Fewest Platforms at a Station

MediumGreedySortingTwo pointers153 tests

A railway station gets several trains in one day. You are given two arrays of the same length, arrivals and departures. Train i arrives at arrivals[i] and leaves at departures[i].

Each time is one integer in the form HHMM. For example, 905 means 9:05 and 1430 means 14:30. All times are on the same day, and arrivals[i] <= departures[i].

A train stays on its platform from its arrival time to its departure time, and both times are included. So if one train leaves at 1000 and another train arrives at 1000, the two trains need two different platforms.

Return the minimum number of platforms the station needs so that no train has to wait.

Note

The trains are not given in any special order.
Because all times are on the same day, you can compare two HHMM values as plain integers.

Hint: sort the arrival times and the departure times as two separate lists. Then walk through both lists in time order and keep a count of the trains that are at the station right now.

Examples

Example 1

Input:: [815,840,1000,1110,1505,1800], [830,1200,1130,1145,1900,2000]
Output:: 3

From 11:10 to 11:30 three trains are at the station: the one from 8:40 to 12:00, the one from 10:00 to 11:30 and the one from 11:10 to 11:45. No moment has four trains.

Example 2

Input:: [700,930], [930,1015]
Output:: 2

The first train leaves at 9:30 and the second arrives at 9:30. Both ends are included, so at 9:30 both trains use a platform.

Example 3

Input:: [1300,600,2200], [1350,645,2310]
Output:: 1

No two trains are at the station at the same time, so one platform is enough.

Constraints

1 <= arrivals.length == departures.length <= 20
Every time is a valid HHMM value from 0 (00:00) to 2359 (23:59).
arrivals[i] <= departures[i]

Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.