Minimum Railway Platforms

MediumProblemExternal linkUpdated Oct 2, 2026

Description

You are given two arrays representing the arrival and departure times of trains at a railway station. Each pair arr[i] and dep[i] indicates that the i-th train arrives at time arr[i] and departs at time dep[i], with times given in 24-hour format (HHMM) as integers.

A train occupies a platform from its arrival until its departure. If two or more trains are at the station at the same time, each one requires a separate platform. Find the minimum number of platforms needed so that no train has to wait for a platform to become available.

Examples

Example 1

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]

Output: 3

Explanation: Between times 1100 and 1120, three trains are at the station simultaneously: the train that arrived at 940 (departs at 1200), the train that arrived at 950 (departs at 1120), and the train that arrived at 1100 (departs at 1130). Each of these three trains needs its own platform, so the minimum number of platforms required is 3.

Example 2

Input: arr = [900, 1235, 1100], dep = [1000, 1240, 1200]

Output: 1

Explanation: No two trains are at the station at the same time. The first train (900-1000) departs before the third train (1100-1200) arrives, and the third train departs before the second train (1235-1240) arrives. Since all trains can use the same platform sequentially, only 1 platform is needed.

Example 3

Input: arr = [1000, 935, 1100], dep = [1200, 1240, 1130]

Output: 3

Explanation: All three trains are at the station during the period 1100-1130. Train 1 (935-1240) and train 0 (1000-1200) are both present when train 2 (1100-1130) arrives. Since all three overlap simultaneously, three separate platforms are required.

Constraints

1 ≤ n ≤ 10^5
0 ≤ arr[i] ≤ dep[i] ≤ 2359
Times are in 24-hour HHMM format

Editorial

Brute Force

Intuition

Imagine you are a station manager watching trains come and go. The simplest way to figure out how many platforms you need is to check, for every single train, how many trains are at the station at the moment it arrives.

Think of it like standing on the platform when each train arrives and counting how many other trains you can see. The train that "sees" the most neighbors tells you the minimum platforms needed.

Formally, train j is at the station when train i arrives if arr[j] ≤ arr[i] ≤ dep[j] (train i itself counts too). The largest such count is the answer: the number of trains at the station only goes up when a train arrives, so the busiest moment always begins with an arrival.

Be careful not to count every train that overlaps train i's whole stay instead. With trains 900–1200, 900–1000 and 1100–1200, the first one overlaps both others, but the two short trains are never at the station together, so only 2 platforms are needed.

Step-by-Step Explanation

Let's trace through with arr = [1000, 935, 1100], dep = [1200, 1240, 1130]:

Step 1: Initialize max_platforms = 0. We have three trains:

Train 0: arrives 1000, departs 1200
Train 1: arrives 935, departs 1240
Train 2: arrives 1100, departs 1130

Step 2: Train 0 arrives at 1000. Who is at the station then? Train 0 itself (1000 ≤ 1000 ≤ 1200) and train 1 (935 ≤ 1000 ≤ 1240). Train 2 has not arrived yet (1100 > 1000). Count = 2. Update max_platforms = 2.

Step 3: Train 1 arrives at 935. Only train 1 itself is there: train 0 arrives at 1000 and train 2 at 1100, both later. Count = 1. max_platforms stays 2.

Step 4: Train 2 arrives at 1100. Train 0 (1000 ≤ 1100 ≤ 1200), train 1 (935 ≤ 1100 ≤ 1240) and train 2 itself are all there. Count = 3. Update max_platforms = 3.

Result: max_platforms = 3. All three trains are at the station at 1100, the moment train 2 arrives, so three platforms are required.

Brute Force — Counting Trains Present at Each Arrival — Watch how we take each train's arrival and count the trains at the station at that moment, to find the peak platform demand.

Algorithm

Initialize max_platforms = 0
For each train i from 0 to n-1:
- Set count = 0
- For each train j from 0 to n-1 (train i included):
  - If arr[j] ≤ arr[i] ≤ dep[j], increment count (train j is at the station when train i arrives)
- Update max_platforms = max(max_platforms, count)
Return max_platforms

Code

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

class Solution {
public:
    int findPlatform(vector<int>& arr, vector<int>& dep) {
        int n = arr.size();
        int maxPlatforms = 0;

        for (int i = 0; i < n; i++) {
            int count = 0;  // trains at the station when train i arrives (itself included)
            for (int j = 0; j < n; j++) {
                if (arr[j] <= arr[i] && arr[i] <= dep[j]) {
                    count++;
                }
            }
            maxPlatforms = max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
};

class Solution:
    def findPlatform(self, arr, dep):
        n = len(arr)
        max_platforms = 0

        for i in range(n):
            count = 0  # trains at the station when train i arrives (itself included)
            for j in range(n):
                if arr[j] <= arr[i] <= dep[j]:
                    count += 1
            max_platforms = max(max_platforms, count)

        return max_platforms

class Solution {
    public int findPlatform(int[] arr, int[] dep) {
        int n = arr.length;
        int maxPlatforms = 0;

        for (int i = 0; i < n; i++) {
            int count = 0;  // trains at the station when train i arrives (itself included)
            for (int j = 0; j < n; j++) {
                if (arr[j] <= arr[i] && arr[i] <= dep[j]) {
                    count++;
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n trains, we check all n trains (itself included): n × n checks, which is O(n²). Each check is two constant-time comparisons.

Space Complexity: O(1)

We only use a few integer variables (count, max_platforms, loop indices). No additional data structures that grow with the input size are needed.

Why This Approach Is Not Efficient

The brute force checks all O(n²) pairs of trains. With n up to 10^5, this means up to 10^10 comparisons — far beyond the roughly 10^8 simple operations allowed per second in typical time limits.

The root cause of inefficiency: for every arrival, we scan the entire array again to see who is present, processing events in no particular order — nothing learned at one arrival is reused at the next.

Key insight: if we sort the arrival and departure events by time, we can process them sequentially and determine the platform count at any moment in O(1) using a simple running counter. This reduces the total time from O(n²) to O(n log n) — dominated by the sorting step.

A log-scale bar chart at n = 10⁵ (axis 10⁵ to 10¹⁰). Brute force, n × n checks: 10¹⁰ (red). Sort + sweep, 2·n·log₂n + 2n: 3.5×10⁶ (green). A dashed amber line at 10⁸ is labelled ≈ 10⁸ per s. The line underneath reads: 100 seconds of checks at 10⁸ per second, against about 35 milliseconds. The title reads: at n = 10⁵ the brute force needs 10¹⁰ checks.

Optimal Approach - Sorting with Two Pointers

Intuition

Instead of checking every pair of trains, think about the problem differently. Imagine you are at the station entrance, watching events happen in real time. Each event is either a train arriving (need one more platform) or a train departing (free one platform). At any moment, the number of occupied platforms equals the total arrivals so far minus the total departures so far.

The trick: we do not need to know WHICH specific train departed — only that SOME train departed. This means we can sort arrivals and departures independently and sweep through both sorted lists simultaneously using two pointers.

At each step, we ask: "What happens next — an arrival or a departure?" If the next arrival time comes before (or at) the next departure time, a train is arriving and needs a platform. Otherwise, a train is leaving and frees one up. The peak platform count during this sweep is our answer.

Step-by-Step Explanation

Let's trace through with arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]:

Step 1: Sort both arrays independently.

sorted_arr = [900, 940, 950, 1100, 1500, 1800]
sorted_dep = [910, 1120, 1130, 1200, 1900, 2000]
Initialize i = 0, j = 0, platforms = 0, max_platforms = 0.

Step 2: Compare arr[0] = 900 with dep[0] = 910. Since 900 ≤ 910, the next event is an arrival.

platforms = 1, max_platforms = 1. Advance i = 1.

Step 3: Compare arr[1] = 940 with dep[0] = 910. Since 940 > 910, a departure happens first.

platforms = 0. Advance j = 1. The first train left before the second arrived.

Step 4: Compare arr[1] = 940 with dep[1] = 1120. Since 940 ≤ 1120, an arrival.

platforms = 1. Advance i = 2.

Step 5: Compare arr[2] = 950 with dep[1] = 1120. Since 950 ≤ 1120, another arrival.

platforms = 2, max_platforms = 2. Advance i = 3.

Step 6: Compare arr[3] = 1100 with dep[1] = 1120. Since 1100 ≤ 1120, another arrival.

platforms = 3, max_platforms = 3. Advance i = 4. This is peak congestion!

Step 7: Compare arr[4] = 1500 with dep[1] = 1120. Since 1500 > 1120, a departure.

platforms = 2. Advance j = 2.

Step 8: Compare arr[4] = 1500 with dep[2] = 1130. Since 1500 > 1130, a departure.

platforms = 1. Advance j = 3.

Step 9: Compare arr[4] = 1500 with dep[3] = 1200. Since 1500 > 1200, a departure.

platforms = 0. Advance j = 4. All trains from the congestion burst have left.

Step 10: Compare arr[4] = 1500 with dep[4] = 1900. Since 1500 ≤ 1900, an arrival.

platforms = 1. Advance i = 5.

Step 11: Compare arr[5] = 1800 with dep[4] = 1900. Since 1800 ≤ 1900, an arrival.

platforms = 2. Advance i = 6. All arrivals processed.

Result: max_platforms = 3, achieved during the mid-morning burst when trains at 940, 950, and 1100 were all present simultaneously.

Sorting + Two Pointer Sweep for Minimum Platforms — Watch how sorting arrivals and departures separately allows a simple two-pointer sweep to track platform count in real time, finding the peak demand efficiently.

Algorithm

Sort the arrival array arr[] in ascending order
Sort the departure array dep[] in ascending order
Initialize two pointers i = 0, j = 0 and counters platforms = 0, max_platforms = 0
While i < n (unprocessed arrivals remain):
- If arr[i] ≤ dep[j] (next event is an arrival):
  - Increment platforms
  - Update max_platforms = max(max_platforms, platforms)
  - Advance i
- Else (next event is a departure):
  - Decrement platforms
  - Advance j
Return max_platforms

Code

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

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

        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;

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

        return maxPlatforms;
    }
};

class Solution:
    def findPlatform(self, arr, dep):
        arr.sort()
        dep.sort()
        n = len(arr)

        platforms = 0
        max_platforms = 0
        i, j = 0, 0

        while i < n:
            if arr[i] <= dep[j]:
                platforms += 1
                max_platforms = max(max_platforms, platforms)
                i += 1
            else:
                platforms -= 1
                j += 1

        return max_platforms

import java.util.Arrays;

class Solution {
    public int findPlatform(int[] arr, int[] dep) {
        int n = arr.length;
        Arrays.sort(arr);
        Arrays.sort(dep);

        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;

        while (i < n) {
            if (arr[i] <= dep[j]) {
                platforms++;
                maxPlatforms = Math.max(maxPlatforms, platforms);
                i++;
            } else {
                platforms--;
                j++;
            }
        }

        return maxPlatforms;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting both the arrival and departure arrays takes O(n log n) each. The two-pointer sweep processes at most 2n events (n arrivals and up to n departures), each in O(1) time, contributing O(n). The total is O(n log n) + O(n) = O(n log n), dominated by sorting.

Space Complexity: O(1)

If we sort the arrays in-place, we use only a constant number of extra variables (i, j, platforms, max_platforms). The auxiliary space is O(1). Note: some sort implementations may use O(log n) stack space internally.