Minimum number of platforms

Medium

Problem

Given the arrival and departure times of trains at a station, return the minimum number of platforms needed so that no train has to wait.

Example 1

Input:  arr = [900, 940, 950, 1100, 1500, 1800], dep = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3

Also asked as: Minimum Platforms Problem

Test cases

Case 1

Input:    [900,940,950,1100,1500,1800], [910,1200,1120,1130,1900,2000]
Expected: 3

Case 2

Input:    [900,1100,1235], [1000,1200,1240]
Expected: 1

Case 3

Input:    [100], [200]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort arrivals and departures separately, sweep

Time O(n log n)Space O(1)

Merge the two sorted time streams; +1 platform on an arrival, −1 on a departure. The running maximum is the answer.

function minPlatforms(arr, dep) {
arr.sort((a, b) => a - b);
dep.sort((a, b) => a - b);
let platforms = 0, best = 0, i = 0, j = 0;
while (i < arr.length) {
if (arr[i] <= dep[j]) { platforms++; i++; best = Math.max(best, platforms); }
else { platforms--; j++; }
}
return best;
}