Minimum Platforms / Resources — Interval Scheduling… | OneNoughtOne

0/86

Data Structures & AlgorithmsInterval Scheduling Patterns

Interval Scheduling Patterns

LevelIntermediate

Duration75 mins

TopicInterval Scheduling Patterns

3 / 4

Minimum Platforms / Resources

The Railway Station Problem

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.

What You Will Learn

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 Formulation

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: Arrival and departure times are given separately (not as pairs, though we can pair them) All times belong to the same day (no overnight considerations in basic version) If a train arrives at time t and another departs at time t, both can use the same platform (instantaneous swap) Platforms are identical—any platform can host any train 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.

Minimum Platforms Example

Classic railway station scenario

Input

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]

Output

Minimum platforms: 3

Explanation

Between 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.

Approach 1: Event Array Sweep

The most elegant approach treats arrivals and departures as events along the timeline: Algorithm: Create an event list: for each train, add (arrival, +1) and (departure, -1) Sort events by time Sweep through, maintaining a running count of "trains currently at station" Track the maximum count observed 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.

minimum_platforms_sweep.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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 usage
arrivals   = [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: 3

Tie-Breaking Nuance

The condition 'arr[i] <= dep[j]' (using \leq) 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.

Approach 2: Prefix Sum on Timeline

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: Create an array platforms[0..MAX_TIME+1] initialized to 0 For each train: platforms[arrival] += 1, platforms[departure + 1] -= 1 Compute prefix sums; the maximum value is our answer Intuition: 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: Time: O(n + T) where T is the time range Space: O(T) Trade-offs: Faster than sorting when n is large relative to T Not suitable when time range is huge (use sorting approach instead) Requires integer times (or discretization for floating-point)

minimum_platforms_prefix.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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
 
 
# Example
arrivals   = [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")

Approach Comparison: When to Use Each
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)

Deeper Analysis: Why This Works

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 \leq min_platforms is impossible; we have min_platforms \geq 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.

The Interval Graph Perspective

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.

Real-World Considerations

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: Offset all times past midnight by 24 hours Detect and handle wrap-around cases 4. Rush Hour vs Average Minimum platforms handles the peak . But building for peak might be wasteful if it's rare. Real planning considers: 95th percentile load (not maximum) Cost of occasional delays vs cost of extra platforms

Extensions for Production Systems

•Dynamic scheduling — Trains can be delayed; recompute assignments in real-time
•Multi-station optimization — Minimize total platforms across a network
•Cost optimization — Platforms have different costs (e.g., covered vs open)
•Priority handling — High-speed trains get preference; model as weighted intervals
•Disruption recovery — When a platform fails, reassign trains minimizing cascading delays

practical_extensions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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()}
 
 
# Example
arrivals   = [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_p

Minimum Platforms in Disguise
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

Common Mistakes and Debugging

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: Usually <= (train can depart and arrive at same instant on same platform) Some problems use strict inequality 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.

Edge Cases Checklist

•Empty input — 0 trains → 0 platforms
•Single train — 1 train → 1 platform
•No overlap — Sequential trains → 1 platform
•All overlap — All trains at same time → n platforms
•Same arrival/departure — Instantaneous visit → still needs 1 platform
•Identical intervals — All [10, 20] → n platforms

edge_case_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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()

Data Structures & AlgorithmsInterval Scheduling Patterns

Interval Scheduling Patterns

LevelIntermediate

Duration75 mins

TopicInterval Scheduling Patterns

3 / 4

Minimum Platforms / Resources

The Railway Station Problem

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.

What You Will Learn

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 Formulation

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: Arrival and departure times are given separately (not as pairs, though we can pair them) All times belong to the same day (no overnight considerations in basic version) If a train arrives at time t and another departs at time t, both can use the same platform (instantaneous swap) Platforms are identical—any platform can host any train 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.

Minimum Platforms Example

Classic railway station scenario

Input

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]

Output

Minimum platforms: 3

Explanation

Between 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.

Approach 1: Event Array Sweep

The most elegant approach treats arrivals and departures as events along the timeline: Algorithm: Create an event list: for each train, add (arrival, +1) and (departure, -1) Sort events by time Sweep through, maintaining a running count of "trains currently at station" Track the maximum count observed 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.

minimum_platforms_sweep.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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 usage
arrivals   = [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: 3

Tie-Breaking Nuance

The condition 'arr[i] <= dep[j]' (using \leq) 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.

Approach 2: Prefix Sum on Timeline

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: Create an array platforms[0..MAX_TIME+1] initialized to 0 For each train: platforms[arrival] += 1, platforms[departure + 1] -= 1 Compute prefix sums; the maximum value is our answer Intuition: 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: Time: O(n + T) where T is the time range Space: O(T) Trade-offs: Faster than sorting when n is large relative to T Not suitable when time range is huge (use sorting approach instead) Requires integer times (or discretization for floating-point)

minimum_platforms_prefix.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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
 
 
# Example
arrivals   = [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")

Approach Comparison: When to Use Each
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)

Deeper Analysis: Why This Works

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 \leq min_platforms is impossible; we have min_platforms \geq 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.

The Interval Graph Perspective

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.

Real-World Considerations

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: Offset all times past midnight by 24 hours Detect and handle wrap-around cases 4. Rush Hour vs Average Minimum platforms handles the peak . But building for peak might be wasteful if it's rare. Real planning considers: 95th percentile load (not maximum) Cost of occasional delays vs cost of extra platforms

Extensions for Production Systems

•Dynamic scheduling — Trains can be delayed; recompute assignments in real-time
•Multi-station optimization — Minimize total platforms across a network
•Cost optimization — Platforms have different costs (e.g., covered vs open)
•Priority handling — High-speed trains get preference; model as weighted intervals
•Disruption recovery — When a platform fails, reassign trains minimizing cascading delays

practical_extensions.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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()}
 
 
# Example
arrivals   = [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_p

Minimum Platforms in Disguise
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

Common Mistakes and Debugging

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: Usually <= (train can depart and arrive at same instant on same platform) Some problems use strict inequality 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.

Edge Cases Checklist

•Empty input — 0 trains → 0 platforms
•Single train — 1 train → 1 platform
•No overlap — Sequential trains → 1 platform
•All overlap — All trains at same time → n platforms
•Same arrival/departure — Instantaneous visit → still needs 1 platform
•Identical intervals — All [10, 20] → n platforms

edge_case_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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()

Minimum Platforms / Resources

The Railway Station Problem

Problem Formulation

Minimum Platforms Example

Approach 1: Event Array Sweep

Approach 2: Prefix Sum on Timeline

Deeper Analysis: Why This Works

Real-World Considerations

Related Problems and Variations

Common Mistakes and Debugging

Minimum Platforms / Resources

The Railway Station Problem

Problem Formulation

Minimum Platforms Example

Approach 1: Event Array Sweep

Approach 2: Prefix Sum on Timeline

Deeper Analysis: Why This Works

Real-World Considerations

Related Problems and Variations

Common Mistakes and Debugging

Minimum Platforms / Resources

The Railway Station Problem

Problem Formulation

Approach 1: Event Array Sweep

Approach 2: Prefix Sum on Timeline

Deeper Analysis: Why This Works

Real-World Considerations

Related Problems and Variations

Common Mistakes and Debugging

There’s more to understand.

Minimum Platforms / Resources

The Railway Station Problem

Problem Formulation

Approach 1: Event Array Sweep

Approach 2: Prefix Sum on Timeline

Deeper Analysis: Why This Works

Real-World Considerations

Related Problems and Variations

Common Mistakes and Debugging

There’s more to understand.