How many platforms the station needs
Reported in interviews at (where)
A station knows when each of its trains will arrive and leave during one day, in minutes after midnight. Train i arrives at minute arrival[i] and leaves at minute departure[i], and it holds a platform for every minute from its arrival to its departure, both included. So a train that arrives in the same minute another one leaves needs a platform of its own.
For each day, find the fewest platforms the station needs so that no train ever waits for one.
Input
The first line holds T, the number of tests. Each test is three lines: n, the number of trains; then the n arrival minutes; then the n departure minutes, in the same train order.
Output
For each test, one line: the fewest platforms that station needs.
- Input
3
5
540 545 550 600 600
560 547 600 610 605
2
100 200
150 250
3
0 0 0
0 0 0- Output
3
1
3
- At minute 600 the third train is still in, since it leaves that minute, while the fourth and fifth arrive.
- The first train has gone before the second arrives.
- All three trains are in during minute 0.
Limits
1 <= T <= 1001 <= n <= 100000the n of all the tests add up to at most 4000000 <= arrival[i] <= departure[i] <= 1439
Hints
Hint 1
Which train leaves when does not matter for the count: sort the arrivals and the departures separately.
Hint 2
Walk both sorted lists together. If the next arrival is not after the next departure, a train comes in: one more platform in use. Otherwise one leaves. The answer is the most ever in use.
Where this was reported
- Deutsche Bank, Graduate analyst on-campus interview, 2023 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
