PROBLEM STATEMENT
You want to travel by train from one station to another. Unfortunately there is no direct train,
so you have to transfer a number of times. Transferring happens instantaneously. We'll number the
stations as follows: 0 is the departure station, 1 ... N-1 are the transfer stations (in that
order) and N is the destination station.
You know the timetable of the trains travelling from station i to station i+1. It is given as a
vector timeTable. The i-th element (indexed from 0) of timeTable describes the trains
from station i to station i+1 and contains one or more parts of the form "hh:mm-HH:MM" separated
by single spaces. Here "hh:mm" and "HH:MM" are times in 24 hour notation. "hh:mm" is valid 24 hour
notation if both "hh" and "mm" contain exactly 2 digits and 00<=hh<24 and 00<=mm<60.
If there is a part "hh:mm-HH:MM" in the i-th element of timeTable, this means that every day a
train leaves from station i at time "hh:mm" and arrives at station i+1 at time "HH:MM". If "HH:MM"
is later than "hh:mm" the train arrives on the same day; if it is earlier it arrives on the next
day. If the two times are equal, the train takes exactly 24 hours and arrives the next day. No
train will take more than 24 hours.
On day 1 you are at station 0 at 09:00. What is the earliest time you can get to station N? Return
the time in the following format "hh:mm, day d", with "hh:mm" the time in 24 hour notation and "d"
the day, with no leading zeroes.
DEFINITION
Class:TravellingByTrain
Method:earliestArrival
Parameters:vector
Returns:string
Method signature:string earliestArrival(vector timeTable)
CONSTRAINTS
-timeTable contains between 1 and 50 elements, inclusive
-Each element of timeTable has length between 1 and 50, inclusive, and is formatted as described
in the statement.
EXAMPLES
0)
{"10:00-13:00 12:00-15:00","11:00-16:00 14:00-19:00"}
Returns: "19:00, day 1"
You're at station 0 at 09:00, at station 1 at 13:00 and finally at station 2 at 19:00.
1)
{"09:00-13:57","13:56-17:00"}
Returns: "17:00, day 2"
You just catch the train at station 0, but miss the train at station 1, so you have to wait until
the next day to catch the next train.
2)
{"10:00-08:00"}
Returns: "08:00, day 2"
If the arrival time is earlier than the departure time, the train arrives at that time the next day.
3)
{"09:10-11:00 09:05-10:05","10:10-12:00 11:00-11:05","17:00-08:00","09:00-08:00"}
Returns: "08:00, day 3"
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.