277. How Many Platforms
Challenge1000 ms256 MBSolved by 0%
n trains arrive and depart at a station. Print the smallest number of
platforms needed so that no train ever waits.
A train occupies a platform from its arrival to its departure inclusive, so a train arriving at the exact moment another departs still needs its own platform.
The trains are given as two separate lists, and which arrival belongs to which departure does not matter. Sort each list independently and sweep: every arrival takes a platform, every departure frees one, and the answer is the largest number in use at any moment.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ arrival ≤ departure ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n arrival times.
The third line contains n departure times.
Output
Print one integer, the minimum number of platforms required.
Input6
900 940 950 1100 1500 1800
910 1200 1120 1130 1900 2000
Output3
Noteis the standard timetable example, peaking at three
Input1
900
910
Output1
Noteis a single train
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution