Problem statement

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

A platform can hold only one train at a time, and a train arriving at exactly the moment another departs still needs its own platform.

Example 1

Input: arrival = [900,940,950,1100,1500,1800], departure = [910,1200,1120,1130,1900,2000]
Output: 3
Explanation: Between 950 and 1100 three trains are at the station.

Example 2

Input: arrival = [900,1100,1235], departure = [1000,1200,1240]
Output: 1

Example 3

Input: arrival = [100,200], departure = [200,300]
Output: 2
Explanation: The second train arrives exactly as the first departs.

Constraints

• 1 <= arrival.length <= 40
• departure.length == arrival.length
• 0 <= arrival[i] <= departure[i] <= 2359

Hints for Minimum Number of Platforms

1. Hint 1

   Trains do not need to be matched to each other — only the count present at any moment matters.

2. Hint 2

   Sort the arrivals and the departures separately and sweep both with two pointers.

3. Hint 3

   An arrival at or before the next departure occupies a new platform; otherwise a platform frees up.

How to solve Minimum Number of Platforms

Trains need not be matched — only how many are present at any moment matters. Sort arrivals and departures separately and sweep with two pointers.

Approach

1. Sort both arrays.
2. While arrivals remain: if arr[i] <= dep[j], a train arrives — increment platforms and i, update the max; else a train leaves — decrement platforms and j.
3. Return the maximum.

Why it works

The number of trains present at time t is arrivals ≤ t minus departures < t; the merge of the two sorted streams visits every event in time order and the running count peaks at the answer. <= counts an arrival coinciding with a departure as needing its own platform.

Complexity

• Time — O(n log n)
• Space — O(1) beyond the sorts

Pitfalls

• Using < instead of <= under-counts when a train arrives exactly as another leaves.

Reference solution

Python

def findPlatform(arrival, departure) -> int:
    arr = sorted(arrival)
    dep = sorted(departure)
    i = j = platforms = best = 0
    while i < len(arr):
        if arr[i] <= dep[j]:
            platforms += 1
            i += 1
            best = max(best, platforms)
        else:
            platforms -= 1
            j += 1
    return best

Java

public static int findPlatform(int[] arrival, int[] departure) {
    int[] arr = arrival.clone();
    int[] dep = departure.clone();
    Arrays.sort(arr);
    Arrays.sort(dep);
    int i = 0, j = 0, platforms = 0, best = 0;
    while (i < arr.length) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
            best = Math.max(best, platforms);
        } else {
            platforms--;
            j++;
        }
    }
    return best;
}

C++

int findPlatform(vector<int>& arrival, vector<int>& departure) {
    vector<int> arr = arrival;
    vector<int> dep = departure;
    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());
    int i = 0, j = 0, platforms = 0, best = 0;
    while (i < (int) arr.size()) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
            best = max(best, platforms);
        } else {
            platforms--;
            j++;
        }
    }
    return best;
}

JavaScript

var findPlatform = function(arrival, departure) {
    const arr = arrival.slice().sort(function(a, b) { return a - b; });
    const dep = departure.slice().sort(function(a, b) { return a - b; });
    let i = 0, j = 0, platforms = 0, best = 0;
    while (i < arr.length) {
        if (arr[i] <= dep[j]) {
            platforms++;
            i++;
            if (platforms > best) best = platforms;
        } else {
            platforms--;
            j++;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium