Minimum Number of Platforms in DSA Python - Build from Scratch

Minimum Number of Platforms

📖 Scenario: Imagine a busy train station where multiple trains arrive and depart at different times. To avoid delays, the station needs enough platforms so that no train has to wait for another to leave.

🎯 Goal: You will write a program to find the minimum number of platforms needed at the station so that all trains can arrive and depart without waiting.

📋 What You'll Learn

Create two lists called arrivals and departures with exact train arrival and departure times.

Create a variable called platforms_needed to count platforms required at any time.

Write a loop to find the minimum number of platforms needed using the arrival and departure times.

Print the final minimum number of platforms needed.

💡 Why This Matters

🌍 Real World

Train stations and airports use this logic to manage platforms and gates efficiently to avoid delays.

💼 Career

Understanding scheduling and resource allocation is important for software engineers working on transportation, event planning, or operating systems.

1

Create arrival and departure time lists

Create a list called arrivals with these exact values: 900, 940, 950, 1100, 1500, 1800. Also create a list called departures with these exact values: 910, 1200, 1120, 1130, 1900, 2000.

DSA Python

# Create the arrivals and departures lists with given times
# Your code here

Hint

Use square brackets to create lists and separate numbers with commas.

2

Initialize platform counter and sort times

Create a variable called platforms_needed and set it to 1. Also create a variable called max_platforms and set it to 1. Sort the arrivals list and the departures list using the sort() method.

DSA Python

arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
# Create platforms_needed and max_platforms variables and sort arrivals and departures
# Your code here

Hint

Use variable = 1 to create counters and list.sort() to sort lists.

3

Calculate minimum platforms needed

Create two variables i and j and set both to 1 and 0 respectively. Use a while loop that runs while i is less than the length of arrivals and j is less than the length of departures. Inside the loop, if arrivals[i] is less than or equal to departures[j], increase platforms_needed by 1 and increase i by 1. Otherwise, decrease platforms_needed by 1 and increase j by 1. After each change, update max_platforms to be the maximum of itself and platforms_needed.

DSA Python

arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
platforms_needed = 1
max_platforms = 1
arrivals.sort()
departures.sort()
# Use a while loop with i and j to calculate platforms needed
# Your code here

Hint

Use two pointers i and j to compare arrivals and departures.

4

Print the minimum number of platforms needed

Print the value of max_platforms.

DSA Python

arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
platforms_needed = 1
max_platforms = 1
arrivals.sort()
departures.sort()
i = 1
j = 0
while i  max_platforms:
            max_platforms = platforms_needed
    else:
        platforms_needed -= 1
        j += 1
# Print the max_platforms value
# Your code here

Hint

Use print(max_platforms) to show the result.

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