Minimum Number of Platforms in DSA Go - 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

↓

Repeat until all trains processed

↓

Return max platforms needed

Sort arrival and departure times, then use two pointers to track overlapping trains and find max platforms needed.

Execution Sample

DSA Go

arrivals := []int{900, 940, 950, 1100, 1500, 1800}
departures := []int{910, 1200, 1120, 1130, 1900, 2000}
// Find minimum platforms needed

This code finds the minimum number of platforms needed so 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	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	Platforms: 1 (Train at 900 arrived)
3	Compare arrival[1]=940 < departure[0]=910	1	0	0	1	Platforms: 0 (Train at 910 departed)
4	Compare arrival[1]=940 < departure[1]=1120	1	1	1	1	Platforms: 1 (Train at 940 arrived)
5	Compare arrival[2]=950 < departure[1]=1120	2	1	2	2	Platforms: 2 (Train at 950 arrived)
6	Compare arrival[3]=1100 < departure[1]=1120	3	1	3	3	Platforms: 3 (Train at 1100 arrived)
7	Compare arrival[4]=1500 < departure[1]=1120	4	1	2	3	Platforms: 2 (Train at 1120 departed)
8	Compare arrival[4]=1500 < departure[2]=1130	4	2	1	3	Platforms: 1 (Train at 1130 departed)
9	Compare arrival[4]=1500 < departure[3]=1200	4	3	0	3	Platforms: 0 (Train at 1200 departed)
10	Compare arrival[4]=1500 < departure[4]=1900	4	4	1	3	Platforms: 1 (Train at 1500 arrived)
11	Compare arrival[5]=1800 < departure[4]=1900	5	4	2	3	Platforms: 2 (Train at 1800 arrived)
12	Compare arrival end, process remaining departures	6	4	1	3	Platforms: 1 (Train at 1900 departed)
13	Process departure[5]=2000	6	5	0	3	Platforms: 0 (Train at 2000 departed)
14	All trains processed	-	-	0	3	Final max platforms needed: 3

💡 All trains processed, max platforms needed is 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	After Step 12	After Step 13	Final
i (arrival index)	0	1	1	2	3	3	4	4	4	4	5	6	6	6
j (departure index)	0	0	1	1	1	2	2	3	3	4	4	4	5	6
Current Platforms	0	1	0	1	2	3	2	1	0	1	2	1	0	0
Max Platforms	0	1	1	1	2	3	3	3	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 2 where platforms increase to 1.

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 3 where platforms decrease to 0.

Why do we keep track of max platforms separately?

Because current platforms can go up and down, but max platforms records the highest number needed at any time. See variable_tracker Max Platforms row.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, how many platforms are currently needed?

A 1

B 3

C 2

D 4

💡 Hint

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

At which step does the number of platforms first decrease to zero?

A Step 9

B Step 5

C Step 3

D Step 12

💡 Hint

Look for the first step where 'Current Platforms' is 0 in execution_table.

If the arrival time at index 4 was 1300 instead of 1500, how would max platforms change?

A It would decrease

B It would increase

C It would stay the same

D Cannot determine

💡 Hint

Consider how earlier arrival affects overlapping trains and max platforms 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 process
- 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. We use two pointers to traverse these sorted lists. When a train arrives before the earliest departure, we increase the platform count. When a train departs before or at the arrival of the next train, we decrease the platform count. We keep track of the maximum number of platforms needed at any time during this process. The final maximum is the answer. This method efficiently counts overlapping trains to find the minimum platforms required.

Practice

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

easy

A. The earliest train arrival time

B. The total number of trains arriving in a day

C. The longest time a train stays on a platform

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

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 D

4. Quick Check:

   Minimum platforms = no waiting trains [OK]

Hint: Count overlapping trains to find minimum platforms needed [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 Go code snippet correctly declares slices for arrival and departure times for the Minimum Number of Platforms problem?

easy

A. arrivals := [900, 940, 950]; departures := [910, 1200, 1120]

B. arrivals := []int{900, 940, 950}; departures := []int{910, 1200, 1120}

C. arrivals := (900, 940, 950); departures := (910, 1200, 1120)

D. arrivals := {900, 940, 950}; departures := {910, 1200, 1120}

Solution

1. Step 1: Recall Go slice syntax

   In Go, slices are declared with []int{values}, not with parentheses or braces alone.

2. Step 2: Match correct syntax

   arrivals := []int{900, 940, 950}; departures := []int{910, 1200, 1120} uses []int{...} which is correct; others use invalid syntax.

3. Final Answer:

   arrivals := []int{900, 940, 950}; departures := []int{910, 1200, 1120} -> Option B

4. Quick Check:

   Go slices use []int{...} [OK]

Hint: Use []int{...} to declare slices in Go [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Using braces {} without []int type
• Confusing arrays and slices syntax

3. What is the minimum number of platforms required for trains with arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000]?

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Sort arrival and departure times

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

2. Step 2: Count overlapping trains

   Between 940 and 1120, three trains overlap (940, 950, 1100 arrivals with departures after 940). So minimum platforms = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max overlap = 3 trains [OK]

Hint: Sort times and count overlaps to find max platforms [OK]

Common Mistakes:

• Not sorting times before counting
• Counting total trains instead of overlaps
• Mixing arrival and departure times

4. Given this Go code snippet for Minimum Number of Platforms, what is the bug?

arrivals := []int{900, 940, 950}
departures := []int{910, 1200, 1120}
i, j, platforms := 0, 0, 0
for i < len(arrivals) && j < len(departures) {
  if arrivals[i] <= departures[j] {
    platforms++
    i++
  } else {
    platforms--
    j++
  }
}
fmt.Println(platforms)

medium

A. platforms should not be decremented when a train departs

B. The loop should run until i < len(arrivals) only

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

D. platforms variable should be initialized to 1

Solution

1. Step 1: Understand platform counting logic

   When arrival time equals departure time, we should consider the train has left before the next arrives to avoid extra platform count.

2. Step 2: Fix comparison operator

   Using <= causes increment even when arrival equals departure, inflating platform count. Changing to < fixes this.

3. Final Answer:

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

4. Quick Check:

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

Hint: Use strict less than (<) to avoid counting equal times as overlap [OK]

Common Mistakes:

• Using <= instead of < in time comparison
• Incorrect loop termination conditions
• Wrong initialization of platform count

5. You have arrival times [900, 940, 950, 1100, 1500, 1800] and departure times [910, 1200, 1120, 1130, 1900, 2000]. How would you modify the algorithm to also return the time intervals when the maximum number of platforms are needed?

hard

A. Track intervals when platform count reaches max during iteration

B. Sort only arrival times and print max arrival time intervals

C. Count total trains and divide by 2 to get intervals

D. Use a queue to store trains and print all arrival times

Solution

1. Step 1: Track platform count and max count during iteration

   While iterating sorted arrivals and departures, keep updating current platform count and record when it reaches a new maximum.

2. Step 2: Record time intervals for max platforms

   Store the start time when max platforms count is reached and end time when it decreases, to get intervals.

3. Final Answer:

   Track intervals when platform count reaches max during iteration -> Option A

4. Quick Check:

   Record max platform count intervals while counting platforms [OK]

Hint: Save start/end times when platform count hits max [OK]

Common Mistakes:

• Ignoring departure times when tracking intervals
• Only sorting arrivals without departures
• Using total trains count instead of overlaps