Minimum Platforms — Editorial

Opening the reading…

Intuitionwhy the answer is the largest number of trains present together

A platform is occupied from a train's arrival through its departure, including both endpoints because an arrival at the exact departure time still overlaps. Therefore, the required number of platforms is the largest number of train intervals covering the same moment. You do not need to decide which particular platform each train receives; only the number currently occupied matters.

The original pairing between arr[i] and dep[i] identifies each train, but it is not needed to count simultaneous trains. Sort all arrivals and all departures independently. Then compare the next event on each list: an arrival at or before the next departure increases the number of occupied platforms, while a strictly later arrival can reuse the platform released by that departure. The largest active count is the answer.

Equal timestamps are processed as an arrival first, because they count as an overlap.

Approach

Sort the arrival times and departure times independently, because the overlap count depends on event order rather than on which arrival belongs to which departure.

Set i and j to the first unprocessed arrival and departure, and set current and answer to zero so the sweep has an explicit count of occupied platforms and its largest value.

While an arrival remains, compare arr[i] with dep[j]. The next event determines whether a train starts using a platform before any platform can be released.

If arr[i] <= dep[j], process the arrival first, increment current, update answer, and advance i; using <= is required because equal timestamps count as overlapping.

Otherwise, process the departure, decrement current, and advance j, because that platform is free before the later arrival is considered.

Return answer after all arrivals have been processed; every platform demand is caused by an arrival, so no later departure can increase the required maximum.

Complexitythe cost of ordering events and scanning them once

MEASURE	BOUND	WHY
Time	O(n log n)	Sorting the n arrivals and n departures costs O(n log n) in total, and the two pointers each move only forward, so the scan processes at most 2n events without revisiting one.
Space	O(1) extra, excluding the input arrays	The scan uses four integer variables and the sorting is in place for the supplied vectors. The returned integer has constant output size, and the bound does not degrade with any input shape.

Here n is the number of trains. The output is one integer, so it adds no output-storage term to the extra-space bound.

Annotated solutionC++ · sorted two-pointer sweep · complete judge-ready implementation

CPPSort both event lists, process equal-time arrivals first, and retain the maximum active-platform count.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int minPlatforms(vector<int>& arr, vector<int>& dep) {
        sort(arr.begin(), arr.end());
        sort(dep.begin(), dep.end());

        int i = 0;
        int j = 0;
        int current = 0;
        int answer = 0;
        int n = static_cast<int>(arr.size());

        while (i < n) {
            if (arr[i] <= dep[j]) {
                ++current;
                answer = max(answer, current);
                ++i;
            } else {
                --current;
                ++j;
            }
        }

        return answer;
    }
};

The placement of the comparison and update is the core of the solution. An arrival is counted before answer is updated, because the new train needs a platform immediately. A departure only reduces current; it cannot create a larger requirement. Since every arrival is paired with a departure no earlier than itself, the departure pointer remains valid whenever the loop still has an arrival to process.