1. One-Liner
Minimum platforms merges arrival and departure timelines: when a train arrives before the next departure, increase occupancy; track the maximum concurrent trains.
2. The Problem It Solves
Trains have arrival and departure times (same day, no overnight trick in basic form). Find the smallest number of platforms so no two trains share a platform while present.
3. The Core Idea
At any instant, needed platforms = trains currently at station. Sorting events and sweeping counts overlaps—like counting max stacked intervals on one line.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Sort | arr[] ascending; dep[] ascending |
| 2. Two pointers | i on arrivals, j on departures |
| 3. Rule | If arr[i] ≤ dep[j], train arrives → need++ ; else one leaves → need-- |
| 4. Answer | Max value of active count during sweep |
5. Dry Run Example
Trains overlap peaks at some hour—sweep shows peak active = min platforms.
6. Key Properties
| Property | Value |
|---|---|
| Event sweep | Classic |
| Edge cases | Equal times—define ≤ carefully |
7. Where It Is Used
| Domain | Use |
|---|---|
| Rail ops | Platform planning |
| Interviews | Merge-interval cousin |
8. Interview Tips
Don’t double-sort pairs naively wrong; two sorted arrays trick is standard. Alternative: line sweep on events.
9. Comparison with Other Approaches
| Approach | Notes |
|---|---|
Sweep O(n log n) | Optimal |
| Per-minute buckets | Only if times quantized |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) sorting |
| Space | O(1) extra beyond arrays |
Implementation Example (PYTHON)
def min_platforms(arr, dep):
arr.sort()
dep.sort()
i = j = need = ans = 0
n = len(arr)
while i < n and j < n:
if arr[i] <= dep[j]:
need += 1
ans = max(ans, need)
i += 1
else:
need -= 1
j += 1
return ans