Loading learning content...
Imagine you're designing a railway station. Trains arrive and depart throughout the day. Each train needs a dedicated platform for the duration of its stop—from arrival to departure. What's the minimum number of platforms needed so that no train ever has to wait?
This is the Minimum Platforms Problem—a classic disguise of Meeting Rooms II. While structurally identical, the railway framing offers fresh intuition, emphasizes capacity planning, and connects to real infrastructure design.
In this page, we'll see that the same algorithmic core solves both problems, explore why the problem appears under different names, dive deeper into the mechanics of platform scheduling, and examine real-world scaling and design considerations.
By the end of this page, you will understand the minimum platforms problem formulation, recognize its equivalence to meeting rooms, implement optimized solutions using multiple approaches, analyze time and space complexity thoroughly, apply this pattern to broader resource allocation scenarios, and appreciate the engineering considerations beyond raw algorithms.
Problem Statement (Minimum Platforms)
Given n trains with their arrival times arr[] and departure times dep[], find the minimum number of platforms required at the station so that no train has to wait.
Constraints and Assumptions:
t and another departs at time t, both can use the same platform (instantaneous swap)Mathematical Formulation:
We have n intervals [arr[i], dep[i]]. Find the smallest k such that we can assign each interval to one of k resources where no resource is used by overlapping intervals.
This is precisely Meeting Rooms II with different variable names.
Arrivals: [9:00, 9:40, 9:50, 11:00, 15:00, 18:00]
Departures: [9:10, 12:00, 11:20, 11:30, 19:00, 20:00]Minimum platforms: 3Between 9:50 and 11:10, three trains are present: Train 2 (9:40-12:00), Train 3 (9:50-11:20), and Train 4 (11:00-11:30). This peak overlap of 3 determines the answer.
Why Does This Problem Appear Separately?
Although structurally identical to Meeting Rooms II, the Minimum Platforms problem is often presented independently for several reasons:
Historical Context — Railway scheduling predates conference room software; the problem was formalized first in transportation logistics.
Input Format Differences — Often arrivals and departures are given as separate arrays, requiring a pairing step or adjustment to standard approaches.
Interview Variation — Interviewers test pattern recognition: can you see Meeting Rooms II inside a railway problem?
Real-World Scale — Railway systems have unique considerations (platform types, switching tracks) that may layer on the basic problem.
The most elegant approach treats arrivals and departures as events along the timeline:
Algorithm:
(arrival, +1) and (departure, -1)Tie-Breaking:
When an arrival and departure happen at the same time, process the departure first. This reflects that a departing train frees its platform instantly before the arriving train needs one.
This is identical to the chronological sweep from Meeting Rooms II, but framed in railway terminology.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
def min_platforms_event_sweep(arrivals: list[int], departures: list[int]) -> int: """ Find minimum platforms using event-based sweep. arrivals[i] = arrival time of train i departures[i] = departure time of train i Time: O(n log n) for sorting Space: O(n) for event list """ n = len(arrivals) if n == 0: return 0 # Create events: (time, type) # type = +1 for arrival (needs platform) # type = -1 for departure (frees platform) events = [] for i in range(n): events.append((arrivals[i], 1)) # Arrival events.append((departures[i], -1)) # Departure # Sort by time, then by type (departures before arrivals at same time) # -1 < 1, so natural tuple ordering works events.sort(key=lambda x: (x[0], x[1])) platforms_in_use = 0 max_platforms = 0 for time, event_type in events: platforms_in_use += event_type max_platforms = max(max_platforms, platforms_in_use) return max_platforms def min_platforms_two_pointer(arrivals: list[int], departures: list[int]) -> int: """ Two-pointer variant: sort arrivals and departures separately. This is the classic textbook formulation. Time: O(n log n) for sorting Space: O(1) if we can sort in-place (otherwise O(n)) """ n = len(arrivals) if n == 0: return 0 # Sort both arrays arr = sorted(arrivals) dep = sorted(departures) platforms_needed = 0 max_platforms = 0 i = 0 # Pointer for arrivals j = 0 # Pointer for departures while i < n: # If next arrival is before or at next departure if arr[i] <= dep[j]: platforms_needed += 1 max_platforms = max(max_platforms, platforms_needed) i += 1 else: # A train departs, freeing a platform platforms_needed -= 1 j += 1 return max_platforms # Example usagearrivals = [900, 940, 950, 1100, 1500, 1800]departures = [910, 1200, 1120, 1130, 1900, 2000] print(f"Platforms (event sweep): {min_platforms_event_sweep(arrivals, departures)}")print(f"Platforms (two-pointer): {min_platforms_two_pointer(arrivals, departures)}")# Both output: 3The condition 'arr[i] <= dep[j]' (using ≤) means if arrival equals departure time, we process arrival first but then immediately a departure frees a platform. Practically, both orders give the same max count. The key is consistency: don't count the arriving and departing train as both needing platforms simultaneously if they share the time instant.
When time values are bounded to a reasonable range (e.g., 0-2400 for minutes in a day), we can use a difference array approach:
Algorithm:
platforms[0..MAX_TIME+1] initialized to 0platforms[arrival] += 1, platforms[departure + 1] -= 1Intuition:
The difference array technique marks "delta changes" at each time point. The prefix sum at time t equals the number of trains present at time t.
Complexity:
Trade-offs:
n is large relative to T12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
def min_platforms_prefix_sum(arrivals: list[int], departures: list[int], max_time: int = 2400) -> int: """ Find minimum platforms using prefix sum / difference array. Assumes times are integers in range [0, max_time]. Time: O(n + max_time) Space: O(max_time) Best when n >> max_time (many trains, limited time range). """ n = len(arrivals) if n == 0: return 0 # Difference array: delta[t] = net change in train count at time t delta = [0] * (max_time + 2) for i in range(n): arr_time = arrivals[i] dep_time = departures[i] delta[arr_time] += 1 # Train arrives: +1 platform needed delta[dep_time + 1] -= 1 # Train departs AFTER this time: -1 # Compute prefix sums to get actual count at each time current_trains = 0 max_platforms = 0 for t in range(max_time + 1): current_trains += delta[t] max_platforms = max(max_platforms, current_trains) return max_platforms def min_platforms_with_timeline(arrivals: list[int], departures: list[int]) -> tuple[int, list[int]]: """ Also return the timeline of platform usage. Useful for visualization and debugging. """ if not arrivals: return 0, [] max_time = max(max(arrivals), max(departures)) delta = [0] * (max_time + 2) for arr, dep in zip(arrivals, departures): delta[arr] += 1 delta[dep + 1] -= 1 timeline = [] current = 0 max_platforms = 0 for t in range(max_time + 1): current += delta[t] timeline.append(current) max_platforms = max(max_platforms, current) return max_platforms, timeline # Examplearrivals = [900, 940, 950, 1100, 1500, 1800]departures = [910, 1200, 1120, 1130, 1900, 2000] print(f"Platforms: {min_platforms_prefix_sum(arrivals, departures, 2400)}") # 3 # With timeline (useful for debugging)platforms, timeline = min_platforms_with_timeline([100, 200, 300], [400, 350, 500])print(f"Max platforms: {platforms}")print(f"At time 250: {timeline[250]} platforms in use")| Aspect | Sorting (Sweep/Two-Pointer) | Prefix Sum/Difference Array |
|---|---|---|
| Time Complexity | O(n log n) | O(n + T) |
| Space Complexity | O(n) | O(T) |
| Best when... | Time range is huge or continuous | Time range T is bounded and small |
| Works with floats? | Yes (sorting handles any comparable) | No (needs integer indices) |
| Additional output | Can track per-time queries | Gives full timeline of usage |
| Typical use case | General-purpose | Dense time slots (e.g., minute-level) |
Let's rigorously prove the correctness of our approaches.
Claim: The maximum simultaneous train count equals the minimum platforms required.
Proof (Lower Bound):
If at some time t, there are k trains simultaneously at the station, we trivially need at least k platforms—one per train. Thus, max_overlap ≤ min_platforms is impossible; we have min_platforms ≥ max_overlap.
Proof (Upper Bound via Greedy Assignment):
We'll show a greedy assignment uses at most max_overlap platforms.
Algorithm: Process trains in order of arrival time. For each train, assign it to the lowest-numbered platform that is free at its arrival time.
Claim: This never uses more than max_overlap platforms.
Proof: Suppose train T arrives at time t and all platforms 1 through k are occupied. This means k trains are present at time t. If k = max_overlap, we assign T to platform k+1. But then at time t, there are k+1 trains present, contradicting max_overlap = k. Thus, k < max_overlap, and we use at most max_overlap platforms.
Model this as a graph where each train is a node, and edges connect overlapping trains (those that must use different platforms). The minimum platforms equals the graph's chromatic number. For interval graphs, this equals the maximum clique size (max overlap). Greedy coloring by start time achieves the optimal chromatic number!
Why Two-Pointer Works Despite Unpairing Arrivals and Departures:
A subtle question: when we sort arrivals and departures separately, we lose track of which arrival pairs with which departure. How can the algorithm still work?
The key insight: we only care about counts, not identities.
At any moment, the number of trains present equals (arrivals so far) - (departures so far). By processing events in chronological order, we track this count correctly. We don't need to know which trains are present—just how many.
The two-pointer approach exploits this: arr[i] isn't the arrival of the same train as dep[i] after sorting, but that's fine. We're counting, not matching.
Beyond the clean algorithmic problem, real railway stations face additional complexities:
1. Platform Types and Train Compatibility
Not all platforms serve all trains. Express trains might need longer platforms; freight trains might need specific loading facilities. This transforms the problem from "color any node with any color" to "color with constraints."
2. Switching Time Buffer
Trains can't instantly swap—cleaning, boarding, and safety checks require buffer time. If a platform needs 10 minutes between trains:
# Adjust departures by buffer
adjusted_dep = [d + buffer for d in departures]
3. Overnight Scheduling
When trains cross midnight (arrival 23:00, departure 02:00), naive algorithms fail. Solutions include:
4. Rush Hour vs Average
Minimum platforms handles the peak. But building for peak might be wasteful if it's rare. Real planning considers:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
def min_platforms_with_buffer(arrivals, departures, buffer_minutes): """ Minimum platforms with required buffer between consecutive trains. Buffer = time needed for cleaning/prep between trains. """ # Extend each train's "occupation" time by buffer adjusted_deps = [d + buffer_minutes for d in departures] return min_platforms_two_pointer(arrivals, adjusted_deps) def min_platforms_overnight(arrivals, departures): """ Handle overnight schedules (times wrap around midnight). If arrival > departure, the train stays overnight. """ adjusted_arr = [] adjusted_dep = [] for arr, dep in zip(arrivals, departures): if arr > dep: # Train spans midnight: split into two "intervals" # From arrival to midnight adjusted_arr.append(arr) adjusted_dep.append(2400) # From midnight to departure adjusted_arr.append(0) adjusted_dep.append(dep) else: adjusted_arr.append(arr) adjusted_dep.append(dep) return min_platforms_two_pointer(adjusted_arr, adjusted_dep) def platform_usage_histogram(arrivals, departures, granularity=60): """ Generate a histogram of platform usage over the day. Useful for capacity planning beyond just the peak. """ max_time = 2400 delta = [0] * (max_time + 2) for arr, dep in zip(arrivals, departures): delta[arr] += 1 delta[dep + 1] -= 1 # Compute running count current = 0 usage_by_hour = {} for t in range(max_time + 1): current += delta[t] hour = t // 100 # Simplistic hour extraction if hour not in usage_by_hour: usage_by_hour[hour] = [] usage_by_hour[hour].append(current) # Return max usage per hour return {h: max(counts) for h, counts in usage_by_hour.items()} # Examplearrivals = [900, 940, 950, 1100, 1500, 1800]departures = [910, 1200, 1120, 1130, 1900, 2000] print(f"Standard: {min_platforms_two_pointer(arrivals, departures)}")print(f"With 30-min buffer: {min_platforms_with_buffer(arrivals, departures, 30)}") histogram = platform_usage_histogram(arrivals, departures)print(f"Usage by hour: {histogram}") def min_platforms_two_pointer(arrivals, departures): """Helper from earlier.""" n = len(arrivals) if n == 0: return 0 arr = sorted(arrivals) dep = sorted(departures) platforms = 0 max_p = 0 i = j = 0 while i < n: if arr[i] <= dep[j]: platforms += 1 max_p = max(max_p, platforms) i += 1 else: platforms -= 1 j += 1 return max_pThe minimum platforms pattern appears across numerous domains:
1. Merge Intervals Preprocessing
Before counting peaks, we might need to merge overlapping intervals from the same source. This is a separate problem but often combined.
2. Maximum Bandwidth Usage
Network connections are intervals (start to end). Peak simultaneous connections = bandwidth requirement. Same algorithm.
3. Minimum CPUs for Job Scheduling
Jobs have execution windows. Minimum CPUs needed = maximum jobs running simultaneously.
4. Car Parking Spaces
Cars arrive and leave at certain times. Find minimum parking spots needed.
5. Streaming Media Servers
Each stream runs for a duration. How many server instances for peak load?
6. Restaurant Seating
Reservations have start and end times. How many tables needed?
Whenever you see: 'Things arrive and depart; each thing needs a resource while present; find minimum resources for no waiting'—you have a minimum platforms problem. Sort events, sweep timeline, track max concurrent. This pattern is ubiquitous in capacity planning.
| Domain | "Train" | "Platform" | Example Constraint |
|---|---|---|---|
| Conference rooms | Meeting | Room | Meeting Rooms II |
| Airport | Flight | Gate | Gate assignment |
| Cloud computing | VM request | Server | Auto-scaling |
| Restaurant | Party | Table | Reservation system |
| Parking | Car visit | Parking spot | Lot sizing |
| Hospital | Surgery | Operating room | OR scheduling |
When implementing minimum platforms solutions, watch for these issues:
Mistake 1: Wrong Operator for Tie-Breaking
arr[i] < dep[j] vs arr[i] <= dep[j] can change results. The correct choice depends on problem semantics:
<= (train can depart and arrive at same instant on same platform)Mistake 2: Modifying Original Arrays
Sorting arrivals/departures destroys the pairing. If you need to preserve input, sort copies.
Mistake 3: Off-By-One in Prefix Sum
When using delta[dep + 1] -= 1, ensure your array is large enough (MAX_TIME + 2).
Mistake 4: Integer Overflow
If using prefix sums with very large counts, ensure data types handle the range.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
def test_min_platforms(): """Comprehensive edge case tests.""" # Empty assert min_platforms_two_pointer([], []) == 0 # Single train assert min_platforms_two_pointer([900], [910]) == 1 # No overlap (sequential) arr = [100, 200, 300] dep = [150, 250, 350] assert min_platforms_two_pointer(arr, dep) == 1 # Complete overlap (all concurrent) arr = [100, 100, 100] dep = [200, 200, 200] assert min_platforms_two_pointer(arr, dep) == 3 # Back-to-back (boundary case) arr = [100, 200] dep = [200, 300] # At time 200: train 1 departs, train 2 arrives # With <= comparison: 1 platform (can share) assert min_platforms_two_pointer(arr, dep) == 1 # Nested intervals arr = [100, 150, 175] dep = [300, 250, 200] # All three overlap between 175 and 200 assert min_platforms_two_pointer(arr, dep) == 3 # Original example arr = [900, 940, 950, 1100, 1500, 1800] dep = [910, 1200, 1120, 1130, 1900, 2000] assert min_platforms_two_pointer(arr, dep) == 3 print("All tests passed!") def min_platforms_two_pointer(arrivals, departures): """Implementation for testing.""" n = len(arrivals) if n == 0: return 0 arr = sorted(arrivals) dep = sorted(departures) platforms = 0 max_p = 0 i = j = 0 while i < n: if arr[i] <= dep[j]: platforms += 1 max_p = max(max_p, platforms) i += 1 else: platforms -= 1 j += 1 return max_p if __name__ == "__main__": test_min_platforms()The Minimum Platforms problem, while structurally equivalent to Meeting Rooms II, offers a different framing that reinforces the core pattern and connects to real-world infrastructure planning.
arr <= dep).Coming Up Next:
We've handled fixed intervals (known start and end times). But what if events occur as a stream, and we need to make decisions on-the-fly? The Event-Based Sweeping page explores the sweep line paradigm more deeply—handling not just counts but queries, updates, and dynamic scenarios.
You've mastered the minimum platforms problem, understood its equivalence to meeting rooms, explored multiple implementation approaches, and seen real-world extensions. Next, we generalize the event-based sweep technique—a powerful paradigm for solving a wide range of interval and geometric problems.