361. Maximum Trains for Which Stoppage Can Be Provided

A railway station has p platforms. Given the arrival and departure times of n trains, determine the maximum number of trains that can be given a stoppage using this procedure: process trains in increasing order of arrival time; if some currently occupied platform has already been vacated (its train's departure time is at or before the current train's arrival), reuse that platform; otherwise, if a platform is still free, use it; if neither is possible, that train is skipped. Print how many trains get a platform under this procedure.

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). The final line contains p, the number of platforms. Output: Print a single integer - the number of trains given a stoppage under the described procedure.

1 <= n <= 10^5, 1 <= p <= 10^3

This procedure might not always achieve the true theoretical maximum possible trains-with-platforms (a cleverer reordering could occasionally do better) - the problem specifically asks for the result of THIS defined greedy procedure, not an independently-optimized answer.

Given a fixed number of platforms, simulate a specific assignment procedure and count how many trains get a stoppage. Brute force: Try every possible subset of trains and check platform feasibility for each combination - this is combinatorially expensive, when the specific greedy min-heap procedure described directly simulates the intended assignment process. Optimised: A min-heap of currently-occupied platforms' departure times lets you instantly check (via its minimum) whether ANY platform has freed up by the time the next train arrives, and lets you efficiently reuse the EARLIEST-freeing platform rather than checking all p platforms individually - this turns what could be an O(n*p) simulation into O(n log p).

Sort all trains by arrival time once up front, then process them in that fixed order; for each train, still linearly scan the array of p platform departure times to find one that's free or vacated. Sorting removes the need to repeatedly search for the next-earliest arrival, leaving only the per-train linear scan over platforms. Time: O(n log n + n*p) Space: O(p)

Sort trains by arrival time, then maintain a min-heap holding the departure times of currently occupied platforms (its size never exceeds p). For each train, check only the heap's minimum: if it is at or before the current arrival, that platform has been vacated, so pop it and push the new departure, which is exactly the 'reuse a vacated platform' case, and checking just the minimum suffices because if the earliest-departing platform isn't free yet, none are. Otherwise, if the heap has fewer than p entries, push the new departure onto a genuinely free platform; otherwise skip the train. Replacing the linear platform scan with a heap operation drops the per-train cost from O(p) to O(log p). Time: O(n log n + n log p) Space: O(p)

Without sorting the trains first, repeatedly search among the remaining trains for the one with the next-earliest arrival time, then linearly scan all p platform slots to check whether any is either free or already vacated (its train's departure is at or before the current arrival); use the first such slot if found, otherwise skip the train. This directly follows the procedure described, but finding 'next earliest arrival' by repeated scanning and checking all p platforms each time is expensive. Time: O(n^2 + n*p) Space: O(p)

1. Sort trains by ARRIVAL time. 2. Maintain a min-heap of the DEPARTURE times of trains currently holding a platform (capped at size p) - its minimum tells you the earliest a platform frees up. 3. For each train in arrival order: if the heap's minimum departure is <= this train's arrival, pop it and push the new departure (reuse that platform); else if the heap has room, push a new departure (use a free platform); otherwise, skip this train entirely.

Time: O(n log n) for sorting by arrival, plus O(n log p) for the heap-based simulation. Space: O(p), for the heap holding at most p currently-occupied platforms' departure times.

p = 1 (only one platform available), all trains overlapping so only p can be served, and n at its maximum of 10^5 to confirm the heap-based simulation runs efficiently.

Be ready to note this problem defines a SPECIFIC greedy procedure to follow exactly (not 'find the true maximum possible', which could differ) - the problem asks for the outcome of THIS particular process, so faithfully simulating it (rather than trying to independently optimize) is what's actually being tested.