Trains at the station
Find the most trains in the station at once by sorting arrivals and departures separately and sweeping along time. About 12 minutes.
Two sorted lists, one sweep
A station gets trains, each with an arrival time and a departure time. How many platforms are needed so that no train waits? That equals the most trains in the station at the same moment.
The pairs don't matter once you think of it as a story over time: at each arrival the count goes up, at each departure it goes down. So sort all the arrival times in one list and all the departure times in another, and walk through time, always handling whichever event is earlier.
arrivals.sort() departures.sort() here = best = 0 i = j = 0
- most
- 1
- trains
- 1
Time 1: a train arrives. One in the station.
Ties go to the arrival
What if one train arrives at exactly the moment another leaves? In this problem they overlap for that instant, so the arriving train needs a platform before the departing one frees up. Count the arrival first when times are equal.
In the code that means comparing with "less than or equal" when you choose between the next arrival and the next departure.
A train arrives at time 5 and another leaves at time 5. Do they need separate platforms?
- AYes, because both are there at time 5
- BNo, one platform is freed just in time
- CIt depends on how long each train stays
Show the answer
Yes, because both are there at time 5. In this problem a train that leaves at the moment another arrives still counts as present.
Platforms needed
arrivals[i] and departures[i] are the arrival and departure times of train i, where arrivals[i] ≤ departures[i]. A train is in the station from its arrival time to its departure time, including both times. Return the smallest number of platforms needed so that no train has to wait.
arrivals = [1, 2, 4], departures = [3, 5, 6] → 2
0 ≤ trains ≤ 100,000 · 0 ≤ time ≤ 1,000,000,000