L10: Minimum Number of Platforms Required in a Railway Station

1. Problem Statement & Core Objective

You are given $n$ number of incoming trains, each with a specific arrival time and departure time (e.g., Train 1 arrives at 09:00 and departs at 09:20). Your primary objective is to determine the minimum number of platforms required at the railway station such that all $n$ trains can seamlessly arrive and depart without any platform conflicts.

2. Real-Life Analogy: The Railway Station Observation

Real-Life Analogy

Imagine standing outside a busy railway station with a notebook, tracking every single event as the clock ticks forward throughout the day.

• When a train arrives, you need to assign it an open platform, increasing your active platform count.
• When a train departs, its platform becomes vacant, decreasing your active platform count.

By keeping track of how many platforms are simultaneously occupied at any given moment, you can find the peak number of overlapping trains. That peak value represents the minimum number of platforms you need to guarantee that no train is ever left waiting for an open track.

3. Walkthrough of an Example Scenario

Let's trace a sample day with 6 trains and their respective arrival and departure times:

Step-by-Step Chronological Trace:

1. 09:00: Train 1 arrives. (Platforms in use: 1)
2. 09:20: Train 1 departs. (Platforms in use: 0)
3. 09:45: Train 2 arrives. (Platforms in use: 1)
4. 09:55: Train 3 arrives. (Platforms in use: 2)
5. 11:00: Train 4 arrives. (Platforms in use: 3)
6. 11:30: Train 3 departs. (Platforms in use: 2)
7. 11:50: Train 4 departs. (Platforms in use: 1)
8. 12:00: Train 2 departs. (Platforms in use: 0)
9. 15:00: Train 5 arrives. (Platforms in use: 1)
10. 18:00: Train 6 arrives. (Platforms in use: 2)
11. 19:00: Train 5 departs. (Platforms in use: 1)
12. 20:00: Train 6 departs. (Platforms in use: 0)

Maximum Overlap / Peak Platforms Required: 3 (at 11:00 AM when Trains 2, 3, and 4 are simultaneously at the station).

4. Naive Approach: The Brute-Force Intersection Check

Conceptual Overview

The brute-force method looks at each individual train and checks how many other trains overlap (intersect) with its time window. If a train's arrival/departure window overlaps with $k$ other trains, those trains require $k+1$ concurrent platforms.

Why This Fails in Interviews

• Complexity: To check every train against every other train requires nested loops.
• Time Complexity: $\mathcal{O}(n^2)$ quadratic time.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space.
• Verdict: Interviewers will reject $\mathcal{O}(n^2)$ solutions because modern railway systems handle thousands of trains daily, demanding an $\mathcal{O}(n \log n)$ approach.

5. Optimized Approach: Sorting Arrival and Departure Times

The Timeline Mental Model

Instead of comparing every train against every other train, we can decouple the arrival times from the departure times and sort them independently. Why? Because as time marches forward, we only care about events:

• An Arrival event means a platform is acquired (count++).
• A Departure event means a platform is released (count--).

By sorting both arrays, we can sweep through the timeline using a two-pointer approach, processing events in chronological order.

6. Step-by-Step Two-Pointer Algorithm

1. Sort the Arrival Array in ascending order.
2. Sort the Departure Array in ascending order.
3. Initialize two pointers: i = 0 (tracking arrivals) and j = 0 (tracking departures).
4. Initialize count = 0 (current platforms in use) and maxCount = 0 (peak platforms needed).
5. Loop while i < n:
   • If arrival[i] <= departure[j], a new train arrives before the next scheduled departure. Increment count++, update maxCount = max(maxCount, count), and advance i++.
   • If arrival[i] > departure[j], a train departs before the next arrival. Decrement count-- and advance j++.
6. Return maxCount.

7. Complete Code Implementation

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class RailwayPlatformOptimizer {
public:
    int findMinPlatforms(vector<int>& arrival, vector<int>& departure, int n) {
        // Step 1: Sort arrival and departure times independently
        sort(arrival.begin(), arrival.end());
        sort(departure.begin(), departure.end());

        int i = 0; // Pointer for arrivals
        int j = 0; // Pointer for departures

        int count = 0;
        int maxCount = 0;

        // Step 2: Traverse both arrays chronologically
        while (i < n) {
            if (arrival[i] <= departure[j]) {
                // Arrival event happens first
                count++;
                maxCount = max(maxCount, count);
                i++;
            } else {
                // Departure event happens first
                count--;
                j++;
            }
        }

        return maxCount;
    }
};

8. Complexity Analysis

Summary and Key Takeaways

• Problem Nature: Finding the minimum platforms is equivalent to finding the maximum interval overlap (or peak concurrent events).
• Avoid Brute-Force $\mathcal{O}(n^2)$: Comparing every train against every other train leads to quadratic inefficiency.
• Decouple Arrivals and Departures: Separating arrival times from departure times allows independent sorting without losing event correlation.
• Chronological Sweep: Using a two-pointer approach (i for arrival, j for departure) simulates a timeline sweep as the day progresses.
• Platform Acquisition vs. Release: Arrival increases active platform usage (count++), while departure frees up a platform (count--).
• Optimal Time Complexity: Sorting achieves an efficient $\mathcal{O}(n \log n)$ time complexity, making it scalable for large datasets.