TravellingByTrain
SRM 240 · 2005-04-30 · by Jan_Kuipers
SRM 240 · 2005-04-30 · by Jan_Kuipers · Brute Force
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 aString[] 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.
You know the timetable of the trains travelling from station i to station i+1. It is given as a
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