Minimum number of platforms
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
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;}