GreedyProblem 8 of 35
Minimum Platforms Problem
Problem Statement
Given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train is kept waiting.
Constraints:
- 1 ≤ n ≤ 10^5
- 0 ≤ arrival[i] < departure[i] ≤ 2359
Example:
- Input:
arrival = [900, 940, 950, 1100, 1500, 1800],departure = [910, 1200, 1120, 1130, 1900, 2000] - Output:
3 - Explanation: At time 1100, trains 2, 3, 4 are at the station.
Example 2:
- Input:
arrival = [900, 940],departure = [910, 1200] - Output:
1 - Explanation: First train leaves before second arrives.
Approach 1: Brute Force (Check All Intervals)
Intuition
For each train, count how many other trains overlap with it. The maximum overlap at any point gives the minimum platforms needed.
Algorithm
- For each train i, check overlap with all other trains
- Two trains overlap if: arrival[i] <= departure[j] AND arrival[j] <= departure[i]
- Track maximum simultaneous trains
java
import java.util.*;
public class Solution {
public int findPlatforms(int[] arrival, int[] departure) {
int n = arrival.length;
int maxPlatforms = 1;
for (int i = 0; i < n; i++) {
int count = 1;
for (int j = 0; j < n; j++) {
if (i != j) {
if (arrival[j] <= arrival[i] && arrival[i] <= departure[j]) {
count++;
}
}
}
maxPlatforms = Math.max(maxPlatforms, count);
}
return maxPlatforms;
}
}Complexity Analysis
- Time Complexity: O(n^2) - Nested loops checking all pairs
- Space Complexity: O(1) - Only using variables
Approach 2: Sorting + Two Pointers - Optimal
Intuition
Sort arrivals and departures separately. Use two pointers to simulate the timeline: arrival increases platform count, departure decreases it.
Key Insight: We don't need to track which specific train uses which platform. We only need to count how many trains are at the station at any point.
Algorithm
- Sort both arrival and departure arrays
- Use two pointers: one for arrivals, one for departures
- If next event is arrival, increment platform count
- If next event is departure, decrement platform count
- Track maximum platform count
java
import java.util.*;
public class MinimumPlatforms {
public int findPlatforms(int[] arrival, int[] departure) {
int n = arrival.length;
// Sort both arrays
int[] arr = arrival.clone();
int[] dep = departure.clone();
Arrays.sort(arr);
Arrays.sort(dep);
int platforms = 0;
int maxPlatforms = 0;
int i = 0, j = 0;
while (i < n && j < n) {
// If next event is arrival
if (arr[i] <= dep[j]) {
platforms++;
maxPlatforms = Math.max(maxPlatforms, platforms);
i++;
}
// If next event is departure
else {
platforms--;
j++;
}
}
return maxPlatforms;
}
// Using events
public int findPlatformsUsingEvents(int[] arrival, int[] departure) {
int n = arrival.length;
int[][] events = new int[2 * n][2];
for (int i = 0; i < n; i++) {
events[2 * i] = new int[]{arrival[i], 1}; // Arrival
events[2 * i + 1] = new int[]{departure[i], -1}; // Departure
}
// Sort by time; if same time, departure before arrival
Arrays.sort(events, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1]; // -1 (departure) before 1 (arrival)
});
int platforms = 0;
int maxPlatforms = 0;
for (int[] event : events) {
platforms += event[1];
maxPlatforms = Math.max(maxPlatforms, platforms);
}
return maxPlatforms;
}
public static void main(String[] args) {
MinimumPlatforms mp = new MinimumPlatforms();
int[] arrival = {900, 940, 950, 1100, 1500, 1800};
int[] departure = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println("Minimum platforms: " + mp.findPlatforms(arrival, departure));
}
}Dry Run Example
arrival = [900, 940, 950, 1100, 1500, 1800]
departure = [910, 1200, 1120, 1130, 1900, 2000]
After sorting:
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1120, 1130, 1200, 1900, 2000]
i=0, j=0, platforms=0
Step 1: arr[0]=900 <= dep[0]=910
- Arrival! platforms=1, maxPlatforms=1
- i=1
Step 2: arr[1]=940 > dep[0]=910
- Departure! platforms=0
- j=1
Step 3: arr[1]=940 <= dep[1]=1120
- Arrival! platforms=1, maxPlatforms=1
- i=2
Step 4: arr[2]=950 <= dep[1]=1120
- Arrival! platforms=2, maxPlatforms=2
- i=3
Step 5: arr[3]=1100 <= dep[1]=1120
- Arrival! platforms=3, maxPlatforms=3
- i=4
Step 6: arr[4]=1500 > dep[1]=1120
- Departure! platforms=2
- j=2
Step 7: arr[4]=1500 > dep[2]=1130
- Departure! platforms=1
- j=3
Step 8: arr[4]=1500 > dep[3]=1200
- Departure! platforms=0
- j=4
Step 9: arr[4]=1500 <= dep[4]=1900
- Arrival! platforms=1
- i=5
Step 10: arr[5]=1800 <= dep[4]=1900
- Arrival! platforms=2
- i=6 (exit loop)
Result: maxPlatforms = 3
Timeline visualization:
Time: 900 910 940 950 1100 1120 1130 1200 1500 1800 1900 2000
Train 1: [----]
Train 2: [------------------------]
Train 3: [----------]
Train 4: [----------]
Train 5: [----------]
Train 6: [----------]
At 1100: Trains 2, 3, 4 are present = 3 platforms needed
Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(n) for sorted copies (or O(1) if sorting in place is allowed)
Approach 3: Using Difference Array (For Limited Time Range)
Time Complexity: O(n + T) where T is time range
Key Takeaways
- Two Pointers on Sorted Arrays: Sort arrivals and departures separately
- Event Simulation: Arrival = +1, Departure = -1
- Track Maximum: Maximum simultaneous trains = minimum platforms
- Why Separate Sorting Works: We only care about count, not which train uses which platform
- Equal Times: If arrival and departure are equal, count as overlap (train needs platform at that instant)
- Similar Problems: Meeting Rooms II, Car Pooling, Maximum Overlapping Intervals
- Real Application: Railway station design, conference room scheduling