Practice › Greedy
Minimum Platforms
Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, Walmart
Given arrival and departure times of trains (in minutes from midnight), find the minimum number of platforms so no train waits. A train that arrives at the same minute another departs needs a separate platform.
Input
Line 1: n. Line 2: n arrival times. Line 3: n departure times (departure ≥ arrival).
Output
The minimum number of platforms.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ time ≤ 2359
Sort arrivals and departures separately and sweep with two pointers.
Example 1
Input
6 900 940 950 1100 1500 1800 910 1200 1120 1130 1900 2000
Output
3
Example 2
Input
3 900 1100 1235 1000 1200 1240
Output
1
Hints
- The answer is the largest number of trains at the station at the same moment.
- Sort arrivals and departures separately. Sweep: if the next arrival is ≤ the next departure, a platform is taken; otherwise one is freed.
Approach
Sort both lists and merge them like a timeline. If arr[i] <= dep[j], a train arrives before (or at the same minute as) the next departure: platforms++, i++. Otherwise a train leaves: platforms--, j++. Track the maximum. Using <= processes a same-minute arrival before the departure, which matches the rule that it needs a separate platform. Which train leaves doesn't matter, only how many trains are present.
Complexity: O(n log n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> arr(n), dep(n);
for (auto &x : arr) cin >> x;
for (auto &x : dep) cin >> x;
sort(arr.begin(), arr.end());
sort(dep.begin(), dep.end());
int i = 0, j = 0, cur = 0, best = 0;
while (i < n) {
if (arr[i] <= dep[j]) {
cur++;
i++;
best = max(best, cur);
} else {
cur--;
j++;
}
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
arr = sorted(data[1 : n + 1])
dep = sorted(data[n + 1 : 2 * n + 1])
i = j = cur = best = 0
while i < n:
if arr[i] <= dep[j]:
cur += 1
i += 1
best = max(best, cur)
else:
cur -= 1
j += 1
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n], dep = new int[n];
for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
for (int i = 0; i < n; i++) dep[i] = sc.nextInt();
Arrays.sort(arr);
Arrays.sort(dep);
int i = 0, j = 0, cur = 0, best = 0;
while (i < n) {
if (arr[i] <= dep[j]) {
cur++;
i++;
best = Math.max(best, cur);
} else {
cur--;
j++;
}
}
System.out.println(best);
}
}