The problem
Each train is a pair (arrive, depart) with arrive < depart: it is in the station from arrive up to, but not including, depart. A platform can hold one train at a time. Return the fewest platforms that are enough for all the trains.
platforms([(0, 4), (1, 3), (2, 6), (3, 5),
(5, 8), (6, 9), (7, 10)])
# 3: at time 2, three trains are in at once
Times are half-open, as in Python slices: (s, e) includes s but not e. So a train that ends at 5 and one that starts at 5 do not overlap.
That is, a platform is free again the moment its train leaves. The trains can come in any order. Return 0 for an empty list.
Limits
- Up to 200,000 trains. Aim for O(n log n).
Builds on GRDY-3 Interval scheduling.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No trains | Not run | |
| 3 | One train | Not run | |
| 4 | Leaves as the next arrives | Not run | |
| 5 | All at once | Not run | |
| 6 | Not sorted | Not run | |
| 7 | A long stay | Not run | |
| 8 | 200,000 trains | Not run |