Minimum Number of Platforms in DSA Python - Execution Trace

Concept Flow - Minimum Number of Platforms

Sort arrival times

↓

Sort departure times

↓

Initialize pointers i=0, j=0

↓

Compare arrival[i

↓

Increment platforms

↓

Move i or j pointer

↓

Update max platforms

↓

Repeat until all trains processed

Sort arrival and departure times, then use two pointers to track platforms needed by comparing arrivals and departures.

Execution Sample

DSA Python

arrivals = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]

# Find minimum platforms needed

This code finds the minimum number of platforms needed so that no train waits.

Execution Table

Step	Operation	i (arrival idx)	j (departure idx)	Current Platforms	Max Platforms	Visual State
1	Sort arrivals and departures	0	0	0	0	Arrivals: [900, 940, 950, 1100, 1500, 1800] Departures: [910, 1120, 1130, 1200, 1900, 2000]
2	Compare arrival[0]=900 < departure[0]=910	0	0	1	1	Platform needed for train arriving at 900
3	Move i to 1	1	0	1	1	Platforms still 1
4	Compare arrival[1]=940 < departure[0]=910	1	0	1	1	No, arrival > departure, so free platform
5	Move j to 1, decrement platforms to 0	1	1	0	1	Train departed at 910, platform freed
6	Compare arrival[1]=940 < departure[1]=1120	1	1	1	1	New train arrives, platform needed
7	Move i to 2	2	1	1	1	Platforms 1
8	Compare arrival[2]=950 < departure[1]=1120	2	1	2	2	Another train arrives before previous departs, platform needed
9	Move i to 3	3	1	2	2	Platforms 2
10	Compare arrival[3]=1100 < departure[1]=1120	3	1	3	3	Third train arrives before departure, platform needed
11	Move i to 4	4	1	3	3	Platforms 3
12	Compare arrival[4]=1500 < departure[1]=1120	4	1	3	3	No, arrival > departure, free platform
13	Move j to 2, decrement platforms to 2	4	2	2	3	Train departed at 1120, platform freed
14	Compare arrival[4]=1500 < departure[2]=1130	4	2	2	3	No, arrival > departure, free platform
15	Move j to 3, decrement platforms to 1	4	3	1	3	Train departed at 1130, platform freed
16	Compare arrival[4]=1500 < departure[3]=1200	4	3	1	3	No, arrival > departure, free platform
17	Move j to 4, decrement platforms to 0	4	4	0	3	Train departed at 1200, platform freed
18	Compare arrival[4]=1500 < departure[4]=1900	4	4	1	3	New train arrives, platform needed
19	Move i to 5	5	4	1	3	Platforms 1
20	Compare arrival[5]=1800 < departure[4]=1900	5	4	2	3	Another train arrives before departure, platform needed
21	Move i to 6	6	4	2	3	Platforms 2
22	No more arrivals, move j to 5, decrement platforms to 1	6	5	1	3	Train departed at 1900, platform freed
23	No more arrivals, move j to 6, decrement platforms to 0	6	6	0	3	Train departed at 2000, platform freed
24	All trains processed	6	6	0	3	Minimum platforms needed is 3

💡 All trains processed, maximum platforms needed recorded as 3

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
i (arrival index)	0	1	1	2	3	4	4	5	6	6
j (departure index)	0	0	1	1	1	3	4	4	4	6
Current Platforms	0	1	1	2	3	1	0	2	2	0
Max Platforms	0	1	1	2	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we increment platforms when arrival[i] < departure[j]?

Because a train arrives before the earliest departure, so we need an extra platform. See execution_table step 8 where platforms increase from 1 to 2.

Why do we decrement platforms when arrival[i] >= departure[j]?

Because a train departs before or at the arrival of the next train, freeing a platform. See execution_table step 13 where platforms decrease from 3 to 2.

Why do we stop when both i and j reach the length of the arrays?

Because all trains have been processed for arrival and departure, so no more platform changes are needed. See execution_table step 24.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the number of current platforms?

A 3

B 2

C 1

D 0

💡 Hint

Check the 'Current Platforms' column at step 10 in execution_table.

At which step does the maximum number of platforms first reach 3?

A Step 12

B Step 8

C Step 10

D Step 18

💡 Hint

Look at the 'Max Platforms' column in execution_table to find when it first becomes 3.

If the arrival time at index 3 was 1130 instead of 1100, how would the maximum platforms change?

A It would increase to 4

B It would remain 3

C It would decrease to 2

D It would become 1

💡 Hint

Consider how arrival[3] = 1130 compares to departure times and affects platform count in execution_table.

Concept Snapshot

Minimum Number of Platforms:
- Sort arrival and departure times separately.
- Use two pointers i, j for arrivals and departures.
- If arrival[i] < departure[j], increment platforms and i.
- Else, decrement platforms and j.
- Track max platforms during iteration.
- Result is max platforms needed to avoid waiting.

Full Transcript

To find the minimum number of platforms needed at a station so that no train waits, we first sort the arrival and departure times separately. We then use two pointers: one for arrivals and one for departures. We compare the current arrival time with the current departure time. If the arrival is earlier, it means a train has arrived before the previous one left, so we need an extra platform. We increment the platform count and move to the next arrival. If the arrival is later or equal to the departure, it means a train has left, freeing a platform, so we decrement the platform count and move to the next departure. We keep track of the maximum number of platforms needed during this process. When all trains are processed, the maximum platform count is the minimum number of platforms required. This method efficiently calculates the minimum platforms by simulating train arrivals and departures in order.

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