The station platforms
- O(n log n) · Hard
- Full plan
- Python
- JavaScript
- lists
- sorting
- loops
Problem
At Highvale station no train ever waits: a platform is always free when it pulls in. From today's timetable, the stationmaster opens just enough. Write a function that takes arrivals and departures, two lists of integers of the same length (minutes of the day, from 0 to 1439; they may be empty). Train i arrives at arrivals[i] and leaves at departures[i], always at least one minute after arriving. Return an integer: the most trains that are in the station at the same time.
A train holds its platform from the minute it arrives until it leaves, and on the minute it leaves the platform is already free: if another train arrives that same minute, it can use it.
With arrivals [10, 15, 40, 45] and departures [30, 50, 60, 55], at minute 45 the last three are in (the first left at 30): the answer is 3. With no trains, the answer is 0.
Examples
The one from the example
[10, 15, 40, 45], [30, 50, 60, 55] → 3
They never overlap
[0, 20, 40], [10, 30, 50] → 1
One leaves the minute another arrives
[60, 120], [120, 180] → 1
The timetable comes out of order
[300, 100, 200], [400, 350, 250] → 2
No trains
[], [] → 0
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def peak(arrivals, departures):
passJavaScript
function peak(arrivals, departures) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.