Minimum Platforms Problem: Complete Solution and Analysis

1. Introduction and Core Concepts

The minimum platforms problem is a classic greedy algorithm problem that asks a deceptively simple question: given the arrival and departure times of all trains at a station, what is the minimum number of platforms required so that no train has to wait? At first glance, it looks like a scheduling puzzle, but it is fundamentally a resource allocation problem where time intervals compete for a shared, limited resource.

Formally, you are given two arrays arr[] and dep[] of size n, where arr[i] represents the arrival time of the i-th train and dep[i] represents its departure time. A platform is occupied from arrival until departure, inclusive. If a train arrives at the same time another departs, most problem variants require a separate platform because the arriving train needs the platform at that exact moment. The goal is to compute the maximum number of overlapping intervals at any point in time, which directly equals the minimum platforms needed.

Why does the minimum platforms problem matter beyond railway stations? It is the canonical example of interval partitioning, a core concept in greedy algorithms. The same logic governs how operating systems schedule processes on CPUs, how cloud providers allocate virtual machines, how meeting rooms are assigned in an office, and how network bandwidth is provisioned. Understanding this problem builds intuition for a whole class of optimization problems where the objective is to minimize resources while avoiding conflicts. It teaches the critical greedy choice: sorting by time and making locally optimal decisions leads to a globally optimal solution.

The Greedy Choice Property

The minimum platforms problem exhibits both the greedy choice property and optimal substructure. The greedy choice is to always reuse a platform if a train has departed before the next train arrives. There is never a benefit to keeping a platform idle while opening a new one. This choice is safe because any optimal solution can be transformed to include this reuse without increasing the number of platforms.

Unlike dynamic programming problems, we do not need to explore all possibilities. Once we sort arrival and departure times, a single linear scan is sufficient to determine the answer. This efficiency is what makes the greedy approach so powerful for this problem class.

Problem Constraints and Assumptions

Most formulations assume that times are given in a comparable format, such as integers representing minutes since midnight (e.g., 900 for 9:00 AM) or in HHMM format. It is also assumed that for every train, arr[i] <= dep[i], and that n >= 1. The handling of simultaneous arrival and departure is a crucial detail: if arr[i] == dep[j], do we need an extra platform? In the standard railway interpretation, yes, because the platform is considered occupied until the departure moment inclusive. We will explicitly address both variants in the implementation section.

2. How It Works

The intuition behind the optimal solution is to treat arrivals and departures as events on a timeline. Imagine sweeping a vertical line across the day from morning to night. Every time you encounter an arrival, the number of occupied platforms increases by one. Every time you encounter a departure, it decreases by one. The maximum value this counter ever reaches is the answer. This is known as the chronological sweep or two-pointer technique.

To implement this sweep efficiently, we decouple arrivals and departures. Instead of keeping them paired as intervals, we sort the arr[] array and the dep[] array independently in ascending order. We then use two pointers, i for arrivals and j for departures. We compare the next arrival arr[i] with the earliest departure dep[j]. If the arrival happens before or at the same time as the departure, we need a new platform. If the departure happens strictly before the next arrival, we can free a platform and reuse it.

This approach works because sorting gives us the global chronological order of events. We do not need to know which specific train is departing; we only care about the earliest departure time among currently occupied platforms. If the next train arrives after that earliest departure, at least one platform is guaranteed to be free. If it arrives before, all currently occupied platforms are still busy, so we must allocate a new one.

Why Sorting Is Essential

Without sorting, we would have to check every train against every other train to find overlaps, leading to an O(n^2) brute force solution. Sorting reduces the problem to a linear scan after an O(n log n) preprocessing step. The sorted order ensures that when we process events, we are always considering the next event in time, which is the essence of the sweep line algorithm. This is a common pattern in greedy interval problems: sort first, then scan.

Handling Simultaneous Events

The comparison operator determines the handling of simultaneous events. Using arr[i] <= dep[j] to request a new platform means that if a train arrives at 10:00 and another departs at 10:00, we count them as overlapping and need two platforms. Using arr[i] < dep[j] or equivalently dep[j] < arr[i] to free a platform means we allow reuse at the same time instant. Interviewers often clarify this; if not, state your assumption explicitly and handle both cases. For railway platforms, the inclusive interpretation (<=) is standard.

Visualizing the Sweep

Consider arrivals [900, 940, 950] and departures [910, 1200, 1120]. After sorting, arrivals are [900, 940, 950] and departures are [910, 1120, 1200]. At 900, we need 1 platform. At 940, the earliest departure is 910 which is already gone, so we can reuse that platform, staying at 1. At 950, the earliest remaining departure is 1120, which is after 950, so we need a second platform. The maximum is 2. This visualization helps confirm the logic before coding.

3. Implementation

There are multiple ways to implement the minimum platforms problem in Python, ranging from brute force to optimal greedy solutions. Below are four distinct implementations, each illustrating a different algorithmic perspective. All code examples assume arrival and departure times are integers and handle the inclusive overlap case where arrival == departure requires a new platform.

Approach 1: Brute Force O(n^2)

The brute force method checks for each train how many other trains overlap with it. For train i, we count all trains j where arr[j] <= arr[i] <= dep[j]. The maximum count across all i is the answer. While correct, it is inefficient and fails for large inputs, but it is useful for understanding the definition of overlap.

def min_platforms_brute_force(arr, dep):
    """
    Brute force O(n^2) solution.
    For each train, count how many trains are present at its arrival time.
    """
    n = len(arr)
    if n == 0:
        return 0
    
    max_platforms = 0
    # Check overlap at each arrival time
    for i in range(n):
        count = 0
        for j in range(n):
            # Train j overlaps with arrival of train i if it arrived before or at i
            # and departs at or after i
            if arr[j] <= arr[i] and arr[i] <= dep[j]:
                count += 1
        max_platforms = max(max_platforms, count)
    return max_platforms

# Example
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms_brute_force(arr, dep))  # Output: 3

Approach 2: Optimal Two-Pointer After Sorting O(n log n)

This is the most expected solution in interviews. We sort both arrays and scan them with two pointers. It achieves O(n log n) time due to sorting and O(1) extra space if sorting in-place.

def min_platforms_two_pointer(arr, dep):
    """
    Optimal greedy solution using two pointers.
    Time: O(n log n) for sorting, Space: O(1) auxiliary
    Assumes arrival == departure needs new platform (inclusive).
    """
    n = len(arr)
    if n == 0:
        return 0
    
    arr.sort()
    dep.sort()
    
    platforms_needed = 1
    max_platforms = 1
    i = 1  # pointer for arrivals
    j = 0  # pointer for departures
    
    while i < n and j < n:
        # If next arrival is before or at same time as next departure, need new platform
        if arr[i] <= dep[j]:
            platforms_needed += 1
            i += 1
            # Update maximum
            if platforms_needed > max_platforms:
                max_platforms = platforms_needed
        else:
            # A train has departed, free a platform
            platforms_needed -= 1
            j += 1
            
    return max_platforms

# Example with same times
arr2 = [900, 940, 950, 1100, 1500, 1800]
dep2 = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms_two_pointer(arr2, dep2))  # Output: 3

Approach 3: Min-Heap (Priority Queue) O(n log n)

The heap approach is more general and closely mirrors the meeting rooms II problem. We sort trains by arrival time and maintain a min-heap of departure times for trains currently on platforms. The heap size at any time is the number of platforms in use. When the next train arrives after the earliest departure in the heap, we pop the heap to reuse that platform.

import heapq

def min_platforms_heap(arr, dep):
    """
    Heap-based solution. More intuitive for platform assignment tracking.
    Time: O(n log n), Space: O(n) for heap
    """
    n = len(arr)
    if n == 0:
        return 0
    
    # Pair arrivals and departures and sort by arrival
    trains = sorted(zip(arr, dep))
    
    # Min-heap to store departure times of trains currently at platforms
    heap = []
    heapq.heappush(heap, trains[0][1])
    
    for i in range(1, n):
        arrival, departure = trains[i]
        # If earliest departing train leaves before current arrival, reuse platform
        # For inclusive case, need arrival > departure to reuse
        if heap[0] < arrival:
            heapq.heappop(heap)
        # Alternative for non-inclusive (arrival == departure can reuse):
        # if heap[0] <= arrival:
        #     heapq.heappop(heap)
        
        heapq.heappush(heap, departure)
    
    return len(heap)

# Example
arr3 = [900, 940, 950, 1100, 1500, 1800]
dep3 = [910, 1200, 1120, 1130, 1900, 2000]
print(min_platforms_heap(arr3, dep3))  # Output: 3

Approach 4: Event Sweep Line O(n log n)

This method creates a unified list of events where arrivals are +1 and departures are -1, then sorts events by time. It is elegant because it processes all events in chronological order in one pass. The sorting key must handle tie-breaking correctly to enforce the inclusive rule.

def min_platforms_event_sweep(arr, dep):
    """
    Event-based sweep line.
    Create events: (time, delta) where delta = +1 for arrival, -1 for departure.
    Sort by time; for same time, arrivals before departures if inclusive.
    """
    n = len(arr)
    if n == 0:
        return 0
    
    events = []
    for a in arr:
        events.append((a, 1))   # arrival adds a platform
    for d in dep:
        events.append((d, -1))  # departure frees a platform
    
    # Sort by time. For same time, arrival (+1) should come before departure (-1)
    # to count overlap when arr == dep. So sort by (time, -delta)
    events.sort(key=lambda x: (x[0], -x[1]))
    
    current = 0
    max_platforms = 0
    for time, delta in events:
        current += delta
        if current > max_platforms:
            max_platforms = current
            
    return max_platforms

# Test tie case: arrival at 1000, departure at 1000 should need 2 platforms
print(min_platforms_event_sweep([1000, 1000], [1000, 1010]))  # Output: 2
print(min_platforms_event_sweep([900, 940], [910, 1200]))     # Output: 1

4. Step-by-Step Example

Let us walk through a concrete example in detail to solidify the two-pointer logic. Consider the following schedule with 6 trains:

Arrivals: [900, 940, 950, 1100, 1500, 1800]
Departures: [910, 1200, 1120, 1130, 1900, 2000]

After sorting independently, we get:
Sorted Arrivals: [900, 940, 950, 1100, 1500, 1800]
Sorted Departures: [910, 1120, 1130, 1200, 1900, 2000]

We initialize i = 1 (second arrival at 940), j = 0 (first departure at 910), platforms_needed = 1, and max_platforms = 1. The first train at 900 occupies one platform.

Iteration Trace

Step 1: Compare arr[1]=940 vs dep[0]=910. Since 940 > 910, a train has departed before the next arrival. We free a platform: platforms_needed = 0, then we immediately need to handle the arrival? In the standard loop we decrement and move j to 1. Now platforms_needed = 0, j=1. But our loop structure actually decrements then continues; next comparison will increment again. More intuitively, think of it as: departure at 910 frees platform, arrival at 940 reuses it, so count stays at 1. Implementation-wise, we do platforms_needed -=1; j+=1 giving 0, then next loop iteration will increment.

Step 2: Now compare arr[1]=940 vs dep[1]=1120. Since 940 <= 1120, we need a platform: platforms_needed = 1, i=2, max_platforms = 1.

Step 3: Compare arr[2]=950 vs dep[1]=1120. 950 <= 1120, so need another platform: platforms_needed = 2, i=3, max_platforms = 2.

Step 4: Compare arr[3]=1100 vs dep[1]=1120. 1100 <= 1120, need another: platforms_needed = 3, i=4, max_platforms = 3. This is the peak overlap: trains that arrived at 940, 950, and 1100 are all present simultaneously before 1120.

Step 5: Compare arr[4]=1500 vs dep[1]=1120. 1500 > 1120, so free one: platforms_needed = 2, j=2 (dep=1130).

Step 6: Compare arr[4]=1500 vs dep[2]=1130. 1500 > 1130, free: platforms_needed = 1, j=3 (dep=1200).

Step 7: Compare arr[4]=1500 vs dep[3]=1200. 1500 > 1200, free: platforms_needed = 0, j=4 (dep=1900). Next iteration, arr[4]=1500 <= 1900, so platforms_needed=1, i=5.

Step 8: Compare arr[5]=1800 vs dep[4]=1900. 1800 <= 1900, need platform: platforms_needed=2, i=6 ends loop. Final max_platforms = 3.

The answer is 3 platforms. Notice how the maximum occurs between 1100 and 1120 when three trains overlap. This trace shows why the sorted two-pointer method correctly captures the maximum concurrency without explicitly checking every pair.

5. Complexity Analysis

Understanding the time and space trade-offs is crucial for choosing the right implementation and for discussing complexity in interviews. The minimum platforms problem has a lower bound of O(n log n) if sorting is required, because we must order events chronologically.

The brute force approach is simple but scales poorly. For each of the n trains, it scans all n trains to count overlaps, resulting in quadratic time. It uses only constant extra space but is impractical for n > 10,000. The optimal greedy approaches all achieve O(n log n) time, dominated by the sorting step. The linear scan after sorting is O(n).

Space complexity differs between the optimal methods. The two-pointer method can sort in-place and uses O(1) auxiliary space, making it the most memory efficient. The heap and event sweep methods require O(n) additional space to store the heap or event list. If the input arrays must not be mutated, even the two-pointer method will need O(n) space to copy them before sorting.

Best, average, and worst cases are identical for the sorting-based methods because sorting dominates and its complexity does not depend on input distribution (for comparison sorts). An exception is when arrival times are in a small integer range, such as minutes in a day (0-1439). In that case, counting sort can achieve O(n + k) time where k=1440, which is effectively O(n). This optimization is rarely needed but demonstrates awareness of non-comparison sorting.

In practice, the two-pointer method is preferred for its simplicity and optimal space. The heap method is preferred when you also need to assign specific platform numbers to trains, not just count them, because the heap can store platform IDs. The event sweep is conceptually cleanest for explaining the sweep line idea.

6. Variations and Optimizations

The basic minimum platforms problem has several common variations that appear in interviews and real systems. Recognizing them shows depth of understanding.

Variation 1: Different Overlap Definitions

As mentioned, some problems allow reuse when arr[i] == dep[j]. This changes the comparison from <= to <. Always clarify. Another variation gives times as strings like "09:00" or includes dates, requiring parsing to minutes or timestamps before comparison. A robust solution will convert all times to a uniform integer representation first.

Variation 2: Assigning Platform Numbers

Beyond counting, you may need to output which platform each train gets. This requires tracking platform IDs. The heap approach extends naturally: store tuples of (departure_time, platform_id) in the heap. When a train arrives, if the heap top departs before arrival, reuse that platform_id; otherwise allocate a new id. This also solves the problem of minimizing platforms while providing an actual assignment.

Variation 3: K Platforms Available - Can All Trains Be Scheduled?

Instead of finding the minimum, you are given k platforms and asked if the schedule is feasible, or how many trains must be removed. This becomes a decision problem. You can run the same algorithm and check if max_platforms <= k. To maximize trains scheduled with k platforms, you would sort by departure time and greedily schedule, similar to activity selection.

Optimization: Counting Sort for Bounded Time Range

If times are in HHMM format or minutes since midnight, the range is limited to 1440 values. You can use a frequency array of size 1440 to count arrivals and departures per minute, then sweep through the day in O(n + 1440) time. This avoids O(n log n) sorting and is useful for very large n with small time range.

Variation 4: Weighted Platforms or Different Train Types

Some platforms may only accommodate certain train lengths or types. This becomes a bipartite matching or interval partitioning with constraints, which is more complex and may require greedy with additional data structures or even NP-hard formulations if constraints are arbitrary. For interviews, the unweighted version is standard.

7. Real-World Applications

While framed as a railway problem, the minimum platforms abstraction appears everywhere resources are shared over time. The core pattern is: intervals represent resource usage, and we need the peak concurrency to provision capacity.

In cloud computing and web servers, each incoming request or job has a start time and duration, occupying a server thread, container, or virtual machine. The minimum platforms calculation tells DevOps engineers how many server instances to provision to handle peak load without queuing. Auto-scaling groups use this logic to predict required capacity from historical request logs.

In database systems, transaction locks and connection pools are managed similarly. A database connection is acquired at query start and released at commit. The maximum concurrent connections determines the required pool size. Under-provisioning leads to waiting and timeouts; over-provisioning wastes memory.

In networking, bandwidth allocation for calls or data flows, runway scheduling at airports, operating room scheduling in hospitals, and even CPU scheduling in operating systems all map to this problem. Anywhere you have intervals competing for identical resources, the same greedy sweep applies.

Understanding this mapping helps in system design interviews. When asked to design a meeting scheduler, ticket booking system, or resource manager, you can explicitly reference the minimum platforms problem as the underlying algorithm for capacity planning. It also connects to broader concepts like load balancing and concurrency control.

8. Comparison with Alternatives

The minimum platforms problem is often confused with related interval problems. The key distinction lies in the objective: minimum platforms seeks the maximum overlap (resource minimization for all intervals), while others like activity selection seek the maximum number of non-overlapping intervals (throughput maximization).

Activity selection (or interval scheduling) asks for the maximum number of activities that can be performed by a single resource. It sorts by finish time and greedily picks the earliest finishing compatible activity. Minimum platforms, in contrast, allows multiple resources and wants to accommodate all intervals. Meeting Rooms II is essentially the same as minimum platforms but phrased as meeting rooms; the heap solution is most common there.

Interval merging combines overlapping intervals into consolidated blocks, which is useful for summarizing busy times but does not directly give the concurrency count. Understanding these differences prevents applying the wrong greedy strategy.

In an interview, if you are asked for minimum platforms but you implement activity selection, you will undercount resources. If you implement interval merging, you will get the busy periods but not the depth of overlap. The table above helps you quickly choose the correct pattern based on whether the problem requires scheduling all intervals versus selecting a maximum subset.

9. Common Mistakes and Best Practices

Even experienced candidates make subtle errors on this problem. Awareness of pitfalls is as important as knowing the optimal solution.

Mistake 1: Forgetting to sort both arrays independently. A common error is to sort pairs of (arr, dep) together and then try to apply the two-pointer logic. The two-pointer method requires arrivals and departures sorted separately. If you sort pairs, you lose the independent chronological order of departures. Either sort separately for two pointers, or sort pairs by arrival and use a heap.

Mistake 2: Incorrect handling of equality. Using < when the problem expects <= (or vice versa) leads to off-by-one errors. For example, with arr=[1000], dep=[1000] and another train arr=[1000], dep=[1010], the correct answer with inclusive rule is 2, but with exclusive rule it is 1. Always clarify and document your assumption with a comment. In code, make the comparison explicit and add a note.

Mistake 3: Not converting time formats. Input times may be given as strings "09:00", integers like 900, or even as "9:00 AM". Directly comparing strings lexicographically fails. Convert everything to minutes since midnight: hours*60 + minutes. For HHMM integers, extract hours via t // 100 and minutes via t % 100.

Mistake 4: Mutating input arrays unintentionally. Sorting in-place modifies the caller's data. In production code or when the function may be called multiple times, copy the arrays first: arr_sorted = sorted(arr). This uses O(n) extra space but preserves input integrity.

Mistake 5: Edge cases with empty or single train. For n=0, answer is 0; for n=1, answer is 1. Brute force and heap implementations often forget to handle n=0 before accessing trains[0]. Add an early return.

Best Practices

• State your assumption about simultaneous arrival/departure at the start of the function docstring.
• Use sorted() instead of .sort() if you need to preserve inputs, and mention the space trade-off.
• Write helper function to normalize times to integers before main logic.
• Prefer the two-pointer method for counting only, and heap method when assignment is needed.
• Test with cases: overlapping, non-overlapping, all same time, arrival equals departure, and large random inputs against brute force for validation.
• Include complexity analysis in comments to show interviewers you understand trade-offs.

10. Interview Questions

Interviewers use the minimum platforms problem to test greedy thinking, sorting, and heap usage. Here are common follow-up questions and how to approach them.

Q1: What is the minimum number of platforms required? Explain your approach.

This is the standard question. Answer with the two-pointer method: sort arrivals and departures, use two pointers to sweep chronologically, increment count when arrival <= departure else decrement, track maximum. Mention time O(n log n) and space O(1). Be ready to code it on a whiteboard and trace an example. Emphasize why greedy works: reusing the earliest freed platform is always safe.

Q2: How would you handle if arrival and departure times are given as strings like "09:00" and "09:10"? What if a train arrives at 23:50 and departs at 00:20 next day?

For strings, parse to minutes: split by ":", convert to int, compute h*60+m. For overnight trains where dep < arr, add 1440 minutes (24*60) to departure to represent next day. If multiple days are involved, you need date information. Normalize all times to a linear timeline before sorting. This tests your ability to handle real-world input cleaning.

Q3: Can you also tell which train gets which platform? Modify your solution to assign platforms.

Extend the heap solution to store (departure_time, platform_id). Maintain a counter for next platform id and a heap of occupied platforms. For each train sorted by arrival, if heap top departure < arrival, pop and reuse that platform_id; else allocate new id. Keep a mapping from train index to platform_id. Return both max platforms and assignment dictionary. This demonstrates you can go beyond counting to actual scheduling.

Q4: What if there are only K platforms available? How many trains can you schedule at most, and which ones would you drop?

This becomes a scheduling with limited resources problem. One approach: sort trains by arrival, use a max-heap of departure times for scheduled trains. Iterate trains; add current train to heap; if heap size > K, remove the train with the latest departure (it blocks the platform longest). This maximizes the number of trains scheduled with K platforms, similar to scheduling to maximize throughput. Alternatively, sort by departure and greedily schedule if a platform is free, which is optimal for maximizing count with one platform but needs heap for K > 1.

Q5: What is the difference between minimum platforms and activity selection? When would you use each?

Minimum platforms minimizes resources to schedule all intervals; activity selection maximizes intervals scheduled with one resource. Use minimum platforms when all jobs must be done and you can provision resources (e.g., servers, rooms). Use activity selection when you have one resource and want to maximize utilization (e.g., one conference room, one person). The greedy strategies differ: platforms sort by start time and track concurrency, activity selection sorts by end time and picks earliest finishing compatible jobs. Discuss the comparison table from the previous section to show clarity.

Preparing answers to these variations shows you understand not just the code, but the underlying greedy principles and their applications to system design and resource optimization.