Minimum Platforms
Minimum Platforms is a medium intervals problem solved with the line sweep pattern.
The best approach, optimal (sort both lists, sweep with two pointers), runs in O(n log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (count trains present at each arrival) up.
Problem
A railway station receives n trains in a day. Train i arrives at time arr[i] and departs at time dep[i], with times written as four-digit HHMM integers (for example 945 is 09:45). A train occupies one platform from its arrival to its departure, both ends included, so a train arriving at the exact minute another one departs cannot use that platform.
Return the minimum number of platforms the station needs so that no train ever has to wait.
Examples
Example 1
- Input
arr = [1000, 1010, 1015, 1300], dep = [1030, 1020, 1100, 1310]- Output
3- Why
- From 10:15 to 10:20 the first three trains are all at the station; the fourth comes much later.
Example 2
- Input
arr = [800, 900], dep = [900, 930]- Output
2- Why
- The second train arrives at 9:00 while the first is still leaving at 9:00, so they need different platforms.
Example 3
- Input
arr = [600, 700, 800], dep = [630, 730, 830]- Output
1- Why
- No two trains are ever at the station together.
Constraints
1 <= n <= 5 * 10^4where n is the length ofarranddep.0 <= arr[i] <= dep[i] <= 2359; times are written as HHMM.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (count trains present at each arrival) | O(n²) | O(1) |
| Optimal (sort both lists, sweep with two pointers) | O(n log n) | O(n) |
1Brute force (count trains present at each arrival)
O(n²)Every pair of trains is compared.O(1)A couple of counters.The number of trains in the station only goes up at an arrival, so the maximum occurs at some arrival time. For each train i, count the trains j with arr[j] <= arr[i] <= dep[j], which are exactly those standing in the station when train i comes in.
- For each i, set count = 0.
- For each j, if
arr[j] <= arr[i]andarr[i] <= dep[j], count++. - Track the maximum count over all i.
class Solution {
public int minPlatform(int[] arr, int[] dep) {
int n = arr.length, best = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (arr[j] <= arr[i] && arr[i] <= dep[j]) count++;
best = Math.max(best, count);
}
return best;
}
}class Solution:
def minPlatform(self, arr: List[int], dep: List[int]) -> int:
n, best = len(arr), 0
for i in range(n):
count = 0
for j in range(n):
if arr[j] <= arr[i] <= dep[j]:
count += 1
best = max(best, count)
return bestclass Solution {
public:
int minPlatform(vector<int>& arr, vector<int>& dep) {
int n = arr.size(), best = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++)
if (arr[j] <= arr[i] && arr[i] <= dep[j]) count++;
best = max(best, count);
}
return best;
}
};function minPlatform(arr, dep) {
const n = arr.length;
let best = 0;
for (let i = 0; i < n; i++) {
let count = 0;
for (let j = 0; j < n; j++)
if (arr[j] <= arr[i] && arr[i] <= dep[j]) count++;
best = Math.max(best, count);
}
return best;
}2Optimal (sort both lists, sweep with two pointers)
O(n log n)Two sorts, then a linear merge.O(n)The sorted copies (O(1) extra if sorting in place is allowed).Which train arrives or leaves does not matter, only when. Sort the arrival times and the departure times separately, then walk through both in time order like a merge. An arrival increases the number of occupied platforms, a departure decreases it. On a tie the arrival is processed first, because a train leaving at time t still blocks its platform at t.
- Sort
arranddep(copies). - i = j = 0, cur = best = 0.
- While i < n: if
arr[i] <= dep[j], cur++, i++, best = max(best, cur); otherwise cur--, j++. - Return best.
class Solution {
public int minPlatform(int[] arr, int[] dep) {
int[] a = arr.clone(), d = dep.clone();
Arrays.sort(a);
Arrays.sort(d);
int n = a.length, i = 0, j = 0, cur = 0, best = 0;
while (i < n) {
if (a[i] <= d[j]) {
cur++;
i++;
best = Math.max(best, cur);
} else {
cur--;
j++;
}
}
return best;
}
}class Solution:
def minPlatform(self, arr: List[int], dep: List[int]) -> int:
a, d = sorted(arr), sorted(dep)
n = len(a)
i = j = cur = best = 0
while i < n:
if a[i] <= d[j]:
cur += 1
i += 1
best = max(best, cur)
else:
cur -= 1
j += 1
return bestclass Solution {
public:
int minPlatform(vector<int>& arr, vector<int>& dep) {
vector<int> a(arr), d(dep);
sort(a.begin(), a.end());
sort(d.begin(), d.end());
int n = a.size(), i = 0, j = 0, cur = 0, best = 0;
while (i < n) {
if (a[i] <= d[j]) {
cur++;
i++;
best = max(best, cur);
} else {
cur--;
j++;
}
}
return best;
}
};function minPlatform(arr, dep) {
const a = [...arr].sort((x, y) => x - y), d = [...dep].sort((x, y) => x - y);
const n = a.length;
let i = 0, j = 0, cur = 0, best = 0;
while (i < n) {
if (a[i] <= d[j]) {
cur++;
i++;
best = Math.max(best, cur);
} else {
cur--;
j++;
}
}
return best;
}Edge cases to test
- An arrival at exactly the same time as another train's departure (needs an extra platform)
- All trains at the station at the same moment
- Trains that arrive and leave at the same minute
- Input not sorted by arrival time
Hints
Hint 1
The answer is the largest number of trains that are at the station at one instant.
Hint 2
That peak always happens at some arrival time. Can you count, for each arrival, how many trains are present?
Hint 3
Sort arrivals and departures separately and merge them like two sorted lists, processing an arrival before a departure with the same time.
FAQ
What is the best time complexity for Minimum Platforms?
Optimal (sort both lists, sweep with two pointers) runs in O(n log n) time and O(n) extra space. Two sorts, then a linear merge.
Which pattern does Minimum Platforms use?
It is a intervals problem that uses the line sweep pattern. Other problems with the same pattern: Meeting Rooms II, Car Pooling, Employee Free Time.
Is there a brute force solution for Minimum Platforms?
Yes. Brute force (count trains present at each arrival) takes O(n²) time and O(1) space. The number of trains in the station only goes up at an arrival, so the maximum occurs at some arrival time.
Which edge cases should I test for Minimum Platforms?
An arrival at exactly the same time as another train's departure (needs an extra platform); All trains at the station at the same moment; Trains that arrive and leave at the same minute; Input not sorted by arrival time.