Minimum Number of Platforms in DSA Go

Mental Model

We want to find the smallest number of train platforms needed so no train waits. We do this by checking how many trains overlap 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 has to wait for a spot.

Time line ->
Arrivals:  |---|     |----|    |--|
Departures:    |----|      |---|    |---|
Platforms needed depends on how many intervals overlap.

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

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 arrival and departure times in order.

Step 2: Compare first arrival (9:00) with first departure (9:10), arrival < departure, increase platform count to 1

platforms = 1, i=1, j=0

Why: A train arrives before the first one leaves, so we need a platform.

Step 3: Compare arrival 9:40 with departure 9:10, arrival > departure, decrease platform count to 0, move departure pointer

platforms = 0, i=1, j=1

Why: One train left before next arrived, so platform freed.

Step 4: Compare arrival 9:40 with departure 11:20, arrival < departure, increase platform count to 1

platforms = 1, i=2, j=1

Why: Train arrives before previous leaves, need platform.

Step 5: Compare arrival 9:50 with departure 11:20, arrival < departure, increase platform count to 2

platforms = 2, i=3, j=1

Why: Another train arrives before previous leaves, need another platform.

Step 6: Compare arrival 11:00 with departure 11:20, arrival < departure, increase platform count to 3

platforms = 3, i=4, j=1

Why: Yet another train arrives before previous leaves, need another platform.

Step 7: Compare arrival 15:00 with departure 11:20, arrival > departure, decrease platform count to 2, move departure pointer

platforms = 2, i=4, j=2

Why: One train left, freeing a platform.

Step 8: Compare arrival 15:00 with departure 11:30, arrival > departure, decrease platform count to 1, move departure pointer

platforms = 1, i=4, j=3

Why: Another train left, freeing a platform.

Step 9: Compare arrival 15:00 with departure 12:00, arrival > departure, decrease platform count to 0, move departure pointer

platforms = 0, i=4, j=4

Why: Another train left, freeing a platform.

Step 10: Compare arrival 15:00 with departure 19:00, arrival < departure, increase platform count to 1

platforms = 1, i=5, j=4

Why: Train arrives before previous leaves, need platform.

Step 11: Compare arrival 18:00 with departure 19:00, arrival < departure, increase platform count to 2

platforms = 2, i=6, j=4

Why: Another train arrives before previous leaves, need another platform.

Result:

Maximum platforms needed = 3

Annotated Code

DSA Go

package main

import (
	"fmt"
	"sort"
)

type TrainSchedule struct {
	arrivals   []int
	departures []int
}

func minPlatforms(schedule TrainSchedule) int {
	sort.Ints(schedule.arrivals)   // sort arrival times
	sort.Ints(schedule.departures) // sort departure times

	platformsNeeded := 0
	maxPlatforms := 0
	i, j := 0, 0

	for i < len(schedule.arrivals) && j < len(schedule.departures) {
		if schedule.arrivals[i] < schedule.departures[j] {
			platformsNeeded++               // train arrives, need platform
			if platformsNeeded > maxPlatforms {
				maxPlatforms = platformsNeeded // update max
			}
			i++
		} else {
			platformsNeeded--               // train departs, free platform
			j++
		}
	}

	return maxPlatforms
}

func main() {
	// Times in minutes from midnight for simplicity
	arrivals := []int{540, 580, 590, 660, 900, 1080}   // 9:00,9:40,9:50,11:00,15:00,18:00
	departures := []int{550, 690, 690, 720, 1140, 1200} // 9:10,11:30,11:30,12:00,19:00,20:00

	schedule := TrainSchedule{arrivals, departures}
	result := minPlatforms(schedule)
	fmt.Printf("Minimum number of platforms needed: %d\n", result)
}

sort.Ints(schedule.arrivals) // sort arrival times

sort arrivals to process in order

sort.Ints(schedule.departures) // sort departure times

sort departures to process in order

if schedule.arrivals[i] < schedule.departures[j] {

if next train arrives before earliest departure, need platform

platformsNeeded++

increase platform count for arriving train

if platformsNeeded > maxPlatforms { maxPlatforms = platformsNeeded }

update max platforms if current needed is higher

i++

move to next arrival

} else { platformsNeeded--; j++ }

train departs, free platform and move to next departure

Output

Minimum number of platforms needed: 3

Complexity Analysis

Time: O(n log n) because we sort the arrival and departure arrays, then traverse them once

Space: O(n) for storing arrival and departure times

vs Alternative: Naive approach checks every train against every other train leading to O(n^2) time, this approach is more efficient.

Edge Cases

No trains

Returns 0 platforms needed

DSA Go

for i < len(schedule.arrivals) && j < len(schedule.departures) {

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA Go

if schedule.arrivals[i] < schedule.departures[j] {

Trains arrive after all previous trains depart

Only 1 platform needed

DSA Go

else { platformsNeeded--; j++ }

When to Use This Pattern

When you see overlapping intervals and need to find the minimum resources to handle them, use the 'Minimum Number of Platforms' pattern to count overlaps efficiently.

Common Mistakes

Mistake: Not sorting arrival and departure times before processing
Fix: Always sort both arrays to compare times in order

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

Summary

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

Use when scheduling overlapping intervals where resources must be shared without conflict.

Sort arrivals and departures, then count overlaps by comparing times 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 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