Minimum Railway Platforms
mediumPlacement Coding+20 XPTime limit 2s
You know the arrival and departure time of every train that stops at a station today. Find the minimum number of platforms needed so that no train ever waits.
Times are written as HHMM without leading zeros (930 is 09:30, 5 is 00:05). A platform is busy from the arrival minute to the departure minute inclusive: if one train departs at 1000 and another arrives at 1000, they need two platforms.
Input:
- line 1:
n - line 2: the
narrival times - line 3: the
ndeparture times (trainiarrives atarr[i]and departs atdep[i] ≥ arr[i])
Output: the minimum number of platforms.
Constraints: 1 ≤ n ≤ 5·10⁴, 0 ≤ times ≤ 2359.
Think about it: sort the arrivals and the departures separately, then merge them like in merge sort. An arrival (at or before the next departure) needs one more platform; a departure frees one. The answer is the highest count reached.
Sample input 1
6 900 940 950 1100 1500 1800 910 1200 1120 1130 1900 2000
Sample output 1
3
Sample input 2
2 1000 1000 1000 1000
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).