Why Minimum Number of Platforms in DSA Python?

The Big Idea

What if you could instantly know the exact number of platforms needed to keep trains moving without delay?

The Scenario

Imagine a busy train station where many trains arrive and depart at different times. You want to know how many platforms are needed so that no train has to wait for a platform to be free.

The Problem

Trying to check each train's arrival and departure times manually is slow and confusing. You might miss overlaps or count platforms wrongly, causing delays or wasted space.

The Solution

The Minimum Number of Platforms concept helps us quickly find the smallest number of platforms needed by comparing all arrival and departure times in order. This way, we know exactly when platforms are busy or free.

Before vs After

✗ Before

for each train:
  for each other train:
    if times overlap:
      count platform needed

✓ After

sort arrivals and departures
use two pointers to count overlaps
track max platforms needed

What It Enables

This concept lets us efficiently plan platform usage to avoid train delays and optimize station space.

Real Life Example

Railway stations use this method to decide how many platforms to build so trains can arrive and leave smoothly without waiting.

Key Takeaways

Manual checking of train times is slow and error-prone.

Sorting and comparing arrival and departure times simplifies the problem.

We can find the minimum platforms needed to avoid train waiting.

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