Minimum Number of Platforms in DSA Python

Mental Model

We want to find the smallest number of train platforms needed so that no train waits. This means checking how many trains are at the station at the same time.

Analogy: Imagine a parking lot where cars arrive and leave at different times. We want to know the minimum number of parking spots so no car waits for a spot.

Time line:
Arrivals:  |---|   |-----|  |--|
Departures:    |----|    |---|   |--|
Platforms needed:  ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

Dry Run Walkthrough

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]

Goal: Find the minimum number of platforms needed so no train waits.

Step 1: Sort arrivals and departures separately

arrivals = [9:00, 9:40, 9:50, 11:00, 15:00, 18:00]
departures = [9:10, 11:20, 11:30, 12:00, 19:00, 20:00]

Why: Sorting helps us compare events in order of time.

Step 2: Initialize pointers i=0 (arrivals), j=0 (departures), platforms=0, max_platforms=0

i=0, j=0, platforms=0, max_platforms=0

Why: We track how many trains are currently at the station.

Step 3: Compare arrival[i] and departure[j]: 9:00 < 9:10, so a train arrives before the first departs

platforms=1, max_platforms=1, i=1, j=0

Why: One train occupies a platform.

Step 4: Compare arrival[i] and departure[j]: 9:40 > 9:10, so a train departs before next arrival

platforms=0, max_platforms=1, i=1, j=1

Why: A platform frees up as a train leaves.

Step 5: Compare arrival[i] and departure[j]: 9:40 < 11:20, train arrives before next departure

platforms=1, max_platforms=1, i=2, j=1

Why: Another train occupies a platform.

Step 6: Compare arrival[i] and departure[j]: 9:50 < 11:20, another train arrives before departure

platforms=2, max_platforms=2, i=3, j=1

Why: Two trains overlap, need two platforms.

Step 7: Compare arrival[i] and departure[j]: 11:00 < 11:20, another train arrives before departure

platforms=3, max_platforms=3, i=4, j=1

Why: Three trains overlap, need three platforms.

Step 8: Compare arrival[i] and departure[j]: 15:00 > 11:20, train departs freeing platform

platforms=2, max_platforms=3, i=4, j=2

Why: One train leaves, platform count decreases.

Step 9: Compare arrival[i] and departure[j]: 15:00 > 11:30, train departs freeing platform

platforms=1, max_platforms=3, i=4, j=3

Why: Another train leaves, platform count decreases.

Step 10: Compare arrival[i] and departure[j]: 15:00 > 12:00, train departs freeing platform

platforms=0, max_platforms=3, i=4, j=4

Why: Another train leaves, platform count decreases.

Step 11: Compare arrival[i] and departure[j]: 15:00 < 19:00, train arrives

platforms=1, max_platforms=3, i=5, j=4

Why: Train arrives, platform count increases.

Step 12: Compare arrival[i] and departure[j]: 18:00 < 19:00, train arrives

platforms=2, max_platforms=3, i=6, j=4

Why: Another train arrives, platform count increases.

Step 13: Compare arrival[i] and departure[j]: no more arrivals, remaining departures free platforms

platforms=1, max_platforms=3, j=5

Why: Trains depart, platforms free up.

Step 14: Last departure frees last platform

platforms=0, max_platforms=3, j=6

Why: All trains have left, no platforms occupied.

Result:

Final state: max_platforms = 3
Answer: Minimum 3 platforms needed

Annotated Code

DSA Python

class TrainPlatform:
    def min_platforms(self, arrivals, departures):
        arrivals.sort()
        departures.sort()
        i = j = 0
        platforms = max_platforms = 0
        while i < len(arrivals) and j < len(departures):
            if arrivals[i] < departures[j]:
                platforms += 1
                max_platforms = max(max_platforms, platforms)
                i += 1
            else:
                platforms -= 1
                j += 1
        return max_platforms

if __name__ == '__main__':
    arrivals = [900, 940, 950, 1100, 1500, 1800]
    departures = [910, 1120, 1130, 1200, 1900, 2000]
    tp = TrainPlatform()
    print(tp.min_platforms(arrivals, departures))

arrivals.sort() departures.sort()

Sort arrival and departure times to process events in order

while i < len(arrivals) and j < len(departures):

Traverse both lists to compare arrival and departure events

if arrivals[i] < departures[j]: platforms += 1 max_platforms = max(max_platforms, platforms) i += 1

Train arrives before next departure, increase platform count

else: platforms -= 1 j += 1

Train departs before next arrival, decrease platform count

return max_platforms

Return the maximum platforms needed at any time

Output

3

Complexity Analysis

Time: O(n log n) because sorting arrivals and departures takes O(n log n), and the traversal is O(n)

Space: O(1) because we use only a few extra variables, no extra data structures proportional to input

vs Alternative: Naive approach checks each train against all others, O(n^2), this method is efficient by sorting and linear traversal

Edge Cases

No trains (empty arrivals and departures)

Returns 0 platforms needed

DSA Python

while i < len(arrivals) and j < len(departures):

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA Python

if arrivals[i] < departures[j]:

Trains arrive after all others depart (no overlap)

Only one platform needed

DSA Python

else:

When to Use This Pattern

When you need to find how many events overlap in time, use sorting and two pointers to count overlaps efficiently.

Common Mistakes

Mistake: Not sorting arrival and departure times before processing
Fix: Sort both arrays first to process events in chronological order

Mistake: Using <= instead of < in comparison, causing incorrect platform count
Fix: Use strictly less than (<) to count arrivals before departures correctly

Summary

Finds the minimum number of train platforms needed so no train waits.

Use when scheduling overlapping time intervals to find resource needs.

Sort arrivals and departures, then count overlaps with two pointers.

Practice

1. What does the "Minimum Number of Platforms" problem ask you to find given train arrival and departure times?

easy

A. The least number of platforms needed so no train waits

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

D. The earliest train arrival time

Solution

1. Step 1: Understand the problem context

   The problem wants to find how many platforms are needed so that no train has to wait for another to leave.

2. Step 2: Identify the key requirement

   We must find the minimum number of platforms so that all trains can be accommodated without delay.

3. Final Answer:

   The least number of platforms needed so no train waits -> Option A

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

Hint: Focus on overlapping train times to find platform count [OK]

Common Mistakes:

• Confusing total trains with platforms needed
• Ignoring overlapping arrival and departure times
• Thinking about train durations instead of platform count

2. Which of the following Python code snippets correctly sorts the arrival times list named arrivals for the Minimum Number of Platforms problem?

easy

A. arrivals.sort(arrivals)

B. sort(arrivals)

C. arrivals.sort()

D. arrivals.sorted()

Solution

1. Step 1: Recall Python list sorting method

   Python lists have a method called sort() that sorts the list in place.

2. Step 2: Check each option

   arrivals.sort() uses arrivals.sort() which is correct. sort(arrivals) is invalid syntax. arrivals.sorted() uses a non-existent method. arrivals.sort(arrivals) incorrectly passes the list as argument.

3. Final Answer:

   arrivals.sort() -> Option C

4. Quick Check:

   List.sort() is correct method [OK]

Hint: Use list.sort() to sort lists in place [OK]

Common Mistakes:

• Using sort() as a standalone function
• Trying to call sorted() as a method
• Passing the list as argument to sort()

3. What is the minimum number of platforms needed for the following train schedule?
arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Sort arrival and departure times

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

2. Step 2: Use two pointers to count platforms

   Start with i=0 (arrivals), j=0 (departures), platforms=0, max_platforms=0.
   At 900 (arrival), platforms=1.
   At 910 (departure), platforms=0.
   At 940 (arrival), platforms=1.
   At 950 (arrival), platforms=2.
   At 1100 (arrival), platforms=2 (since departure at 1120 is after 1100 but 1130 and 1200 are later).
   Max platforms needed = 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max overlapping trains = 2 [OK]

Hint: Count overlapping trains using sorted arrivals and departures [OK]

Common Mistakes:

• Not sorting times before counting
• Mixing arrival and departure pointers
• Counting platforms incorrectly at overlaps

4. Identify the error in this Python code snippet for finding minimum platforms:

arrivals = [900, 940, 950]
departures = [910, 1200, 1120]
arrivals.sort()
departures.sort()
i = j = 0
platforms = max_platforms = 0
while i < len(arrivals) and j < len(departures):
    if arrivals[i] <= departures[j]:
        platforms += 1
        i += 1
    else:
        platforms -= 1
        j += 1
    max_platforms = max(max_platforms, platforms)
print(max_platforms)

medium

A. The comparison should be arrivals[i] < departures[j], not <=.

B. The loop condition should use 'or' instead of 'and'.

C. The platforms variable should not be incremented.

D. The departures list should not be sorted.

Solution

1. Step 1: Understand the comparison logic

   Using <= means if arrival time equals departure time, it counts as needing a new platform, but usually a train leaving at time t frees the platform for a train arriving at time t.

2. Step 2: Correct the comparison

   Changing <= to < ensures that if arrival equals departure, platform count decreases first, avoiding unnecessary extra platform.

3. Final Answer:

   The comparison should be arrivals[i] < departures[j], not <=. -> Option A

4. Quick Check:

   Use < to avoid counting simultaneous arrival and departure as overlap [OK]

Hint: Use strict less than for arrival vs departure comparison [OK]

Common Mistakes:

• Using <= causes overcounting platforms
• Changing loop condition wrongly to 'or'
• Not sorting departure times

5. Given multiple trains with arrival and departure times, how would you efficiently find the minimum number of platforms needed if the times are in 24-hour format and some trains arrive and depart at the same time? For example:
arrivals = [900, 940, 950, 1100, 1500, 1800, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000, 1800]
Choose the best approach.

hard

A. Use a dictionary to map arrival times to departure times and count keys.

B. Count trains arriving at each time and sum them directly without sorting.

C. Sort arrivals only and count unique times.

D. Sort arrivals and departures, then use two pointers with strict less than comparison for arrival vs departure.

Solution

1. Step 1: Sort both arrival and departure lists

   Sorting helps to process events in chronological order, which is essential for counting overlapping trains.

2. Step 2: Use two pointers with strict comparison

   Use two pointers to traverse arrivals and departures. Use arrivals[i] < departures[j] to decide when to increase or decrease platform count, handling same-time arrivals and departures correctly.

3. Final Answer:

   Sort arrivals and departures, then use two pointers with strict less than comparison for arrival vs departure. -> Option D

4. Quick Check:

   Sorting + two pointers + < comparison = correct approach [OK]

Hint: Sort both lists and use two pointers with strict comparison [OK]

Common Mistakes:

• Ignoring sorting of departures
• Using <= causing overcount
• Trying to count without sorting or pointers