Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Railway Platforms

MEDIUMProblemSolveExternal Links

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 other trains are at the station during its stay.

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, two trains overlap if one arrives before the other departs and vice versa. For each train, we check this overlap condition against every other train and keep a running count. The maximum count across all trains is the answer.

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: Fix train 0 (1000-1200). Count = 1 (itself). Check overlap with others.

Step 3: Compare train 0 with train 1 (935-1240). Is 1000 ≤ 1240 AND 935 ≤ 1200? YES — overlap! Count = 2. Train 1 arrived earlier and is still at the station when train 0 is present.

Step 4: Compare train 0 with train 2 (1100-1130). Is 1000 ≤ 1130 AND 1100 ≤ 1200? YES — overlap! Count = 3. Train 2 arrives during train 0's stay. Update max_platforms = 3.

Step 5: Fix train 1 (935-1240). Count = 1. Check overlap with others.

Step 6: Compare train 1 with train 0 (1000-1200): overlap (symmetric with Step 3). Count = 2.

Step 7: Compare train 1 with train 2 (1100-1130). Is 935 ≤ 1130 AND 1100 ≤ 1240? YES — overlap! Count = 3. max_platforms stays 3.

Step 8: Fix train 2 (1100-1130). Count = 1. Check overlap with others.

Step 9: Compare train 2 with train 0: overlap. Count = 2.

Step 10: Compare train 2 with train 1: overlap. Count = 3. max_platforms stays 3.

Result: max_platforms = 3. All three trains overlap during the window 1100-1130, so three platforms are required.

Brute Force — Checking All Train Overlap Pairs — Watch how we examine each train and check whether every other train overlaps with it, counting simultaneous occupancy to find the peak platform demand.

Algorithm

  1. Initialize max_platforms = 0
  2. For each train i from 0 to n-1:
    • Set count = 1 (counting the train itself)
    • For each other train j from 0 to n-1 where j ≠ i:
      • If arr[i] ≤ dep[j] AND arr[j] ≤ dep[i], increment count (trains overlap)
    • Update max_platforms = max(max_platforms, count)
  3. 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 = 1;

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n; j++) {
                if (i != j && arr[i] <= dep[j] && arr[j] <= dep[i]) {
                    count++;
                }
            }
            maxPlatforms = max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
};
class Solution:
    def findPlatform(self, arr, dep):
        n = len(arr)
        max_platforms = 1

        for i in range(n):
            count = 1
            for j in range(n):
                if i != j and arr[i] <= dep[j] and arr[j] <= dep[i]:
                    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 = 1;

        for (int i = 0; i < n; i++) {
            int count = 1;
            for (int j = 0; j < n; j++) {
                if (i != j && arr[i] <= dep[j] && arr[j] <= dep[i]) {
                    count++;
                }
            }
            maxPlatforms = Math.max(maxPlatforms, count);
        }

        return maxPlatforms;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n trains, we compare it with all other n-1 trains. This gives n × (n-1) comparisons, which simplifies to O(n²). Each overlap check involves 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 for overlap. 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 train, we scan the entire array to count overlaps, processing events in no particular order. We are doing redundant work because the same overlapping relationship is checked from both sides.

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.

Bar chart comparing O(n²) brute force vs O(n log n) sorting approach for n = 100,000
Bar chart comparing O(n²) brute force vs O(n log n) sorting approach for n = 100,000

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

  1. Sort the arrival array arr[] in ascending order
  2. Sort the departure array dep[] in ascending order
  3. Initialize two pointers i = 0, j = 0 and counters platforms = 0, max_platforms = 0
  4. 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
  5. 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.