139. Minimum Number of Platforms Required for a Railway Station

Given the arrival and departure times of n trains at a railway station, find the minimum number of platforms needed so that no train has to wait.

Input: The first line contains an integer n, the number of trains. The second line contains n space-separated arrival times. The third line contains n space-separated departure times (index-aligned with arrivals). Output: Print a single integer - the minimum number of platforms needed so no train waits.

1 <= n <= 10^5

This is a specific instance of the broader 'maximum overlap / interval scheduling' pattern - the same two-pointer merge-of-sorted-endpoints technique applies to many similar 'peak concurrent usage' problems beyond just trains and platforms.

Find the minimum number of platforms needed so no train ever has to wait for one to free up. Brute force: For every train, check against every OTHER train whether their time ranges overlap, then find the maximum number of mutually-overlapping trains at any point - this costs O(n²), too slow for large n. Optimised: Sorting arrivals and departures independently and merging them with two pointers directly simulates the platform count changing over TIME, in the correct chronological order, without ever needing to compare every pair of trains directly - the running counter's maximum value IS the answer.

Build a combined list of 2n timestamped events - a +1 'platform needed' event at each arrival and a -1 'platform freed' event at each departure - sort all events by time (breaking ties so departures are processed before arrivals at the same instant, since a train leaving frees its platform in time for the next), then sweep through in order, maintaining a running count and tracking its maximum. This finds the true peak concurrency in one linear sweep after sorting, but it needs an explicit array of 2n combined event records. Time: O(n log n) Space: O(n)

Sort the arrival times and departure times independently (in place, as two separate arrays), then walk two pointers i and j across them: if arr[i] <= dep[j], a new platform is needed and i advances; otherwise a platform frees up and j advances, tracking the running and maximum platform count throughout. This achieves the same result as the event-sweep approach without ever materialising a combined event list, needing only the two sorted arrays themselves, so it uses no extra space beyond the sort. Time: O(n log n) Space: O(1) extra

For every train, count how many other trains have an arrival time at or before it and a departure time at or after it (i.e. are still occupying a platform at that moment) by comparing it against all n trains directly. The maximum such count over all trains is the number of platforms needed, since that's the largest number of trains ever simultaneously present. This checks every pair of trains directly and is simple to verify, but scales quadratically with the number of trains. Time: O(n^2) Space: O(1)

1. Sort the arrival times and departure times INDEPENDENTLY (as two separate sorted lists). 2. Walk through both sorted lists with two pointers: whenever the next arrival happens BEFORE the next departure, a new platform is needed (increment a counter). 3. Whenever a departure happens before (or at) the next arrival, a platform frees up (decrement the counter) - track the maximum simultaneous platform count needed at any point.

Time: O(n log n), dominated by sorting the two independent time lists - the merge-walk afterward is O(n). Space: O(n), for the two sorted arrays.

all trains overlapping at the same time (needing n platforms), no two trains overlapping (needing 1 platform), and n at its maximum of 10^5 to confirm the two-pointer approach runs efficiently.

Be ready to explain why sorting arrivals and departures SEPARATELY (rather than keeping (arrival,departure) pairs together) is sufficient and even preferable here - since the answer only depends on the RELATIVE ORDER of arrival and departure EVENTS over time, not which specific train each departure belongs to.