Log inSign up
mediumGeeksforGeeksNot Started

Minimum Platforms

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given arrival and departure times of all trains that reach a railway station, represented as two integer arrays arr[] and dep[] of size N.

Find the minimum number of platforms required for the railway station so that no train is kept waiting.

Note: If a train arrives at the same time another train departs, they cannot use the same platform simultaneously (arrival at time T requires a platform before departure at time T vacates it, or as specified by the platform rules: departure must be strictly less than arrival to share a platform).

Example 1 · Example 1: Six Trains:

Input: arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation: Between 11:00 and 11:20, three trains (arr=940, dep=1200; arr=950, dep=1120; arr=1100, dep=1130) are at the station simultaneously. At least 3 platforms are needed.

Constraints:

  • 1 <= N <= 105
  • 0 <= arr[i] <= dep[i] <= 2359

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why decoupling arrival and departure times is valid for concurrent event counting.
  • Distinguish interval scheduling (max non-overlapping) from interval coloring (min resources).
  • Implement the two-pointer sweep algorithm across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find maximum overlapping events concurrently active.
  • Meeting room allocation / server capacity / platform scheduling.
  • No train / meeting can be delayed.

Algorithmic Decision Tree:

  • Max concurrent overlaps -> Separate sort of start and end times + Two Pointers.
  • Max non-overlapping count -> Sort by end times + Earliest finish greedy.

Connected Patterns:

Meeting Rooms IICar PoolingDivide Intervals Into Minimum Number of Groups

1. Pairwise Overlap Counting

Intuition

For each train, iterate through all other trains and count how many overlap with its time window. Take the maximum count.

Algorithm

  1. Step 1: Initialize maxPlatforms = 0.
  2. Step 2: For each train i from 0 to N - 1:
  3. Step 3: Initialize count = 1.
  4. Step 4: For every other train j from 0 to N - 1 (j != i): check if train j overlaps with train i.
  5. Step 5: If overlapping, increment count.
  6. Step 6: Update maxPlatforms = max(maxPlatforms, count), and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findPlatform(int arr[], int dep[], int n) {
10 int maxPlatforms = 1;
11
12 for (int i = 0; i < n; ++i) {
13 int count = 1;
14 for (int j = 0; j < n; ++j) {
15 if (i != j) {
16 // Train j is at the station during train i's arrival
17 if (arr[i] >= arr[j] && arr[i] <= dep[j]) {
18 count++;
19 }
20 }
21 }
22 maxPlatforms = max(maxPlatforms, count);
23 }
24
25 return maxPlatforms;
26 }
27};
28
29int main() {
30 Solution sol;
31 int arr[] = {900, 940, 950, 1100, 1500, 1800};
32 int dep[] = {910, 1200, 1120, 1130, 1900, 2000};
33 int n = sizeof(arr) / sizeof(arr[0]);
34 cout << "Platforms: " << sol.findPlatform(arr, dep, n) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(1)

2. Min-Heap / Priority Queue Simulation

Intuition

Sort trains by arrival time. Use a min-heap to store departure times of currently assigned platforms. Pop from heap when an existing train departs.

Algorithm

  1. Step 1: Pair up each train [arr[i], dep[i]] and sort by arrival time.
  2. Step 2: Initialize a min-heap to hold departure times of occupied platforms.
  3. Step 3: Push the first train's departure time into the heap.
  4. Step 4: For each subsequent train: if arr >= heap.top(), pop heap (platform reused).
  5. Step 5: Push current train's departure time into the heap.
  6. Step 6: Return the maximum size reached by the heap.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int findPlatform(int arr[], int dep[], int n) {
11 vector<pair<int, int>> trains(n);
12 for (int i = 0; i < n; ++i) trains[i] = {arr[i], dep[i]};
13 sort(trains.begin(), trains.end());
14
15 priority_queue<int, vector<int>, greater<int>> minHeap;
16 int maxPlatforms = 0;
17
18 for (int i = 0; i < n; ++i) {
19 while (!minHeap.empty() && minHeap.top() < trains[i].first) {
20 minHeap.pop();
21 }
22 minHeap.push(trains[i].second);
23 maxPlatforms = max(maxPlatforms, (int)minHeap.size());
24 }
25
26 return maxPlatforms;
27 }
28};
29
30int main() {
31 Solution sol;
32 int arr[] = {900, 940, 950, 1100, 1500, 1800};
33 int dep[] = {910, 1200, 1120, 1130, 1900, 2000};
34 int n = sizeof(arr) / sizeof(arr[0]);
35 cout << "Platforms (Heap): " << sol.findPlatform(arr, dep, n) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

3. Two Pointers on Independently Sorted Arrays

Intuition

Sort arr and dep arrays independently. Traverse chronological events with two pointers: increment platform count on arrival, decrement on departure.

Algorithm

  1. Step 1: Sort arr[] in ascending order and dep[] in ascending order.
  2. Step 2: Initialize i = 0 (arrivals pointer), j = 0 (departures pointer).
  3. Step 3: Initialize platformsNeeded = 0 and maxPlatforms = 0.
  4. Step 4: While i < n and j < n: if arr[i] <= dep[j], platformsNeeded++, i++; else platformsNeeded--, j++.
  5. Step 5: At each step, update maxPlatforms = max(maxPlatforms, platformsNeeded).
  6. Step 6: Return maxPlatforms.

Interactive Trace for Minimum Platforms

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compare arr[0]=900 and dep[0]=910
Visual state
Values and pointers at this exact step
pointers
S
arrived
pending
pending
0
↑ i
1
↑ j
2
Check / comparison
arr[0] (900) <= dep[0] (910)
Decision / next transition
Train arrives: needed = 1, maxPlatforms = 1, i = 1.
Why this step matters

Step 1: Compare arr[0]=900 and dep[0]=910. Arrival occurs first! needed = 1, max = 1, advance i.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findPlatform(int arr[], int dep[], int n) {
10 sort(arr, arr + n);
11 sort(dep, dep + n);
12
13 int i = 0, j = 0;
14 int platformsNeeded = 0;
15 int maxPlatforms = 0;
16
17 while (i < n && j < n) {
18 if (arr[i] <= dep[j]) {
19 platformsNeeded++;
20 maxPlatforms = max(maxPlatforms, platformsNeeded);
21 i++;
22 } else {
23 platformsNeeded--;
24 j++;
25 }
26 }
27
28 return maxPlatforms;
29 }
30};
31
32int main() {
33 Solution sol;
34 int arr[] = {900, 940, 950, 1100, 1500, 1800};
35 int dep[] = {910, 1200, 1120, 1130, 1900, 2000};
36 int n = sizeof(arr) / sizeof(arr[0]);
37 cout << "Platforms (Optimal): " << sol.findPlatform(arr, dep, n) << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Pairwise Overlap CountingO(N^2)O(1)For every train i, count how many other trains j have overlapping time intervals [arr[j], dep[j]] that overlap with [arr[i], dep[i]].Nested loop comparing all pairs.
2.Better — Min-Heap / Priority QueueO(N log N)O(N)Sort trains by arrival time. Use a min-heap to track departure times of occupied platforms. If the earliest departing train finishes before current arrival, reuse its platform.Heap operations.
3.Optimal — Two Pointers on Separately Sorted ArraysOptimalO(N log N)O(1) auxiliarySort arr[] and dep[] independently. Advance two pointers i and j. If arr[i] <= dep[j], count++ and i++; else count-- and j++. Keep running maximum.Array sorting.
Back to DSA Sheet