Connection Status:
Competition Arena > TravellingByTrain
SRM 240 · 2005-04-30 · by Jan_Kuipers · Brute Force
Class Name: TravellingByTrain
Return Type: String
Method Name: earliestArrival
Arg Types: (vector<string>)
Problem Statement

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.

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"
4)
{"09:00-09:00"}
Returns: "09:00, day 2"

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TravellingByTrain with a public method string earliestArrival(vector<string> timeTable) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous