Minimum Platforms (Train Schedule)

Problem Statement

Given arrival and departure times of trains, find the minimum number of platforms needed so no train waits. This medium-level greedy problem is about managing a busy station—keep the trains moving!

Example

Input: arr = [900, 940, 950, 1100], dep = [910, 1200, 1120, 1130]

Output: 3 (peak at 950-1100)

Input: arr = [900, 1100], dep = [1000, 1200]

Output: 1 (no overlap)

Code

public class Solution {
    public int minPlatforms(int[] arr, int[] dep) {
        Arrays.sort(arr);
        Arrays.sort(dep);
        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;
        while (i < arr.length) {
            if (arr[i] <= dep[j]) {
                platforms++;
                i++;
                maxPlatforms = Math.max(maxPlatforms, platforms);
            } else {
                platforms--;
                j++;
            }
        }
        return maxPlatforms;
    }
}
            

def min_platforms(arr, dep):
    arr.sort()
    dep.sort()
    platforms = 0
    max_platforms = 0
    i, j = 0, 0
    while i < len(arr):
        if arr[i] <= dep[j]:
            platforms += 1
            i += 1
            max_platforms = max(max_platforms, platforms)
        else:
            platforms -= 1
            j += 1
    return max_platforms
            

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

Explanation

• Greedy Choice: Sort arrivals and departures, track overlapping trains.
• Flow: Increment platforms for arrivals, decrement for departures.
• Example: [900,940,950,1100] → peak at 3 platforms.

Note