Minimum number of platforms and sliding window maximum
Filed under Accolite
Free read 2 of 3Understand the input format of arrival/departure times and confirm whether trains departing and arriving at the same time require separate platforms.
The question
Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.
Constraints
- 1 <= number of trains <= 10^5
- Arrival and departure times are valid integers
- Arrival time can be greater than or equal to departure time
Examples
- Input
- arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
- Output
- 3
- Why
- At 1100, three trains are at the station (arr 940, 950, 1100), requiring 3 platforms.
Approach
Understand the input format of arrival/departure times and confirm whether trains departing and arriving at the same time require separate platforms.
For every time interval, count how many other intervals overlap with it and find the maximum overlap. Time complexity: O(n^2).
Sort arrival and departure times separately. Use two pointers to iterate through both arrays. Increment platform count when arrival <= departure, else decrement. Track the max platforms needed. Time complexity: O(n log n).
Empty arrays, single train, and identical arrival/departure timestamps.
Tips
- What they are testing: Test cases where all trains overlap, when arrivals and departures are interleaved, and when multiple trains arrive/depart at the exact same minute.
- Common mistake: Failing to sort the arrival and departure arrays independently, which breaks the two-pointer greedy counting logic.
Follow-ups
- What is Clustering and how can we calculate the number of clusters?
Related Accolite questions
Collected from public candidate posts and coding forums. Updated Nov 2026.