Fewest Platforms for a Station Timetable
Solve this ProblemA station has a timetable of trains, each with an arrival time and a departure time. A train occupies a platform for its whole stay, including the very moment it departs, so a train that arrives at the exact moment another one leaves still needs a platform of its own. Find the fewest platforms that let every train stop at a platform for its whole stay.
The number of platforms needed equals the largest number of trains in the station at the same moment. Counting the trains present at each arrival works but is quadratic; sorting arrivals and departures separately and sweeping both in time order gets there in O(n log n).
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ arrivals.length ≤ 14, and departures.length equals arrivals.length; train i arrives at arrivals[i] and leaves at departures[i] - ◆
0 ≤ arrivals[i] ≤ departures[i] ≤ 100 - ◆
A train occupies its platform for the whole closed range from its arrival to its departure, inclusive. A train arriving at the exact moment another one departs still needs a different platform - ◆
Return the fewest platforms that let every train stop at a platform for its whole stay
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Count the Trains Present at Every Arrival Moment
BruteThe busiest moment always coincides with some train's arrival (the count of trains present can only increase when a train arrives). So for each train's arrival time t, count how many trains are in the station at t — those with arrival ≤ t ≤ departure — and keep the largest count. The busiest moment decides the number of platforms needed. It is correct but compares every train with every arrival time.
O(n²)O(1)1class Solution {
2 public int fewestPlatforms(int[] arrivals, int[] departures) {
3 int n = arrivals.length;
4 int most = 0;
5 for (int i = 0; i < n; i++) {
6 int t = arrivals[i];
7 int present = 0;
8 for (int j = 0; j < n; j++) {
9 if (arrivals[j] <= t && t <= departures[j]) present++;
10 }
11 most = Math.max(most, present);
12 }
13 return most;
14 }
15}Optimal — Sort Arrivals and Departures, Sweep Both
OptimalSort the arrival times and the departure times separately (which train is which no longer matters — only how many are present). Then sweep through time with two pointers: if the next arrival is at or before the next departure, a train arrives first, so the number of platforms in use goes up (and the running maximum is updated); otherwise the next event is a departure, so the count goes down. The maximum reached is the answer. The "at or before" comparison is what makes a same-moment arrival count as overlapping.
O(n log n)O(n)1class Solution {
2 public int fewestPlatforms(int[] arrivals, int[] departures) {
3 int[] arr = arrivals.clone();
4 int[] dep = departures.clone();
5 Arrays.sort(arr);
6 Arrays.sort(dep);
7 int n = arr.length;
8 int platforms = 0, most = 0, i = 0, j = 0;
9 while (i < n) {
10 if (arr[i] <= dep[j]) {
11 platforms++;
12 i++;
13 most = Math.max(most, platforms);
14 } else {
15 platforms--;
16 j++;
17 }
18 }
19 return most;
20 }
21}