Minimum Number of Platforms Required

A railway station has n trains scheduled, each with an arrival time and a departure time. Determine the minimum number of platforms needed so that every train can be accommodated without any train having to wait for a platform to free up. If one train departs at exactly the same time another arrives, the departing train is assumed to vacate its platform first, so the two trains may share that platform.

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, where the i-th value in each line corresponds to the same train. Output: Print a single integer: the minimum number of platforms required so that no train has to wait.

1 <= n <= 8000 0 <= arrival[i] <= departure[i] <= 10^9 for every train

Separating arrivals and departures into two INDEPENDENTLY sorted lists (rather than keeping them paired per-train) is the key insight - the specific train identity doesn't matter at all for counting how many platforms are simultaneously occupied.

Given train arrival and departure times, find the minimum number of platforms needed so no train ever waits. Brute force: For every train, check how many OTHER trains' time ranges overlap with it directly - this costs O(n²), too slow for large train counts. Optimised: Sorting arrivals and departures SEPARATELY and sweeping them together with two pointers directly simulates 'how many platforms are occupied at any given moment', tracking the PEAK occupancy across the whole sweep - since only the RELATIVE ORDER of events (not which specific train they belong to) matters for counting platforms needed, this is both simpler and more efficient than any pairwise comparison.

1. Sort the ARRIVAL times and DEPARTURE times INDEPENDENTLY - you don't need to keep each time paired with its original train. 2. Sweep through both sorted lists with two pointers: whenever the next arrival happens BEFORE OR AT the same time as the earliest still-pending departure, one MORE platform is needed right now. 3. Otherwise, a platform frees up (that departure is processed) before the new arrival needs one.

Time: O(n log n), dominated by sorting the two lists - the sweep itself is a single O(n) pass. Space: O(n), for the two sorted arrival/departure arrays.

All trains could arrive at the same time (requiring n platforms), or no two trains' schedules could overlap at all (requiring only 1 platform).

Be precise about the tie-breaking rule (a train departing at the exact same time another arrives frees its platform FIRST, so they can share it) - processing departures before arrivals at equal timestamps is what correctly implements this rule.