Minimum Number of Platforms Required | Greedy + Two Pointers

Problem Statement

Given arrival and departure times of trains, find the minimum number of platforms required so that no train waits.

---

Brute Force Intuition

For every train, check how many other trains overlap with it at the station. The maximum overlap at any point gives the answer.

This works but requires checking every train against every other train.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Snippet

int platforms = 1;

for (int i = 0; i < n; i++) {
    int count = 1;

    for (int j = i + 1; j < n; j++) {
        if (!(dep[i] < arr[j] || dep[j] < arr[i])) {
            count++;
        }
    }

    platforms = Math.max(platforms, count);
}

---

Moving Towards the Optimal Approach

Instead of checking overlaps manually, we can sort arrival and departure times separately.

Whenever a train arrives before the earliest departure, we need a new platform.

Whenever a train departs first, a platform becomes free.

---

Greedy Pattern Recognition

Whenever you see:

• Overlapping intervals
• Simultaneous events
• Maximum active elements at a time

Think:

Sort + Two Pointers

---

Optimal Java Solution

import java.util.*;

class Solution {
    static int findPlatform(int arr[], int dep[]) {
        int n = arr.length;

        Arrays.sort(arr);
        Arrays.sort(dep);

        int platforms = 1;
        int maxPlatforms = 1;

        int i = 1, j = 0;

        while (i < n && j < n) {

            if (arr[i] <= dep[j]) {
                platforms++;
                maxPlatforms = Math.max(maxPlatforms, platforms);
                i++;
            } else {
                platforms--;
                j++;
            }
        }

        return maxPlatforms;
    }
}

---

Dry Run

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

900 Arrives -> 1

940 Arrives -> 2
950 Arrives -> 3

910 Departs -> 2

Max = 3

Result

Minimum Platforms Required = 3

---

Complexity Analysis

Metric	Complexity
Time	O(N log N)
Space	O(1)

---

Interview One-Liner

Sort arrivals and departures separately, then use two pointers to track currently occupied platforms.