TopCoder problem "TravellingByTrain" used in SRM 240 (Division I Level One , Division II Level Two)



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 String[] 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:String[]
Returns:String
Method signature:String earliestArrival(String[] timeTable)
(be sure your method is public)
    
 

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"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4455

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6539&pm=4455

Writer:

Jan_Kuipers

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force