A small station schedules n trains. Train i arrives at time arrival[i] and departs at time departure[i], occupying a platform for the closed interval [arrival[i], departure[i]] — both endpoints included. Two trains may not share a platform at any instant when they are both present; in particular, if one train departs at the exact same time another arrives, they overlap at that instant and require separate platforms.
Determine the minimum number of platforms the station needs so that every train can be accommodated.
Line 1: an integer n, the number of trains.
Line 2: n space-separated integers, the arrival times (empty line when n = 0).
Line 3: n space-separated integers, the departure times (empty line when n = 0). It is guaranteed that arrival[i] <= departure[i].
A single integer: the minimum number of platforms required.
Example 1
Input
6 9 4 7 3 12 6 11 6 9 8 13 10
Expected
3
Explanation
Pairing each arrival with its departure, the trains stop during [9,11], [4,6], [7,9], [3,8], [12,13], and [6,10]. Around time 7 the three trains that stop during [7,9], [3,8], and [6,10] are all present simultaneously, so three platforms are required.
Example 2
Input
3 1 2 3 1 2 3
Expected
1
Explanation
Each train arrives and departs at the same instant, occupying [1,1], [2,2], and [3,3] respectively. No two of these instants coincide, so the trains never share a platform and a single platform suffices.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →