A tram terminal must serve n trams in one day. Tram i arrives at time arrival[i] and departs at time departure[i], with arrival[i] ≤ departure[i]. A tram occupies a platform for the whole closed interval [arrival[i], departure[i]], and a platform can hold only one tram at any instant. If one tram departs at exactly the same time another arrives, they still both need the platform at that instant, so they require two different platforms.
Find the minimum number of platforms so that every tram can be served.
Line 1: an integer n.
Line 2: n space-separated integers, the arrival times.
Line 3: n space-separated integers, the departure times.
A single integer: the minimum number of platforms required.
Example 1
Input
3 1 2 4 3 5 6
Expected
2
Explanation
At time 2 the first tram ([1,3]) and the second ([2,5]) are both present, so 2 platforms are needed; no instant needs 3.
Example 2
Input
1 5 9
Expected
1
Explanation
A single tram needs exactly one platform.
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 →