Minimum Number of Platforms in DSA Rust - 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 count platforms needed by comparing arrivals and departures.

Execution Sample

DSA Rust

let arrivals = [900, 940, 950, 1100, 1500, 1800];
let departures = [910, 1120, 1130, 1200, 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	Compare arrival[0]=900 and departure[0]=910	0	0	1	1	Platforms: [Train at 900 arrives]
2	arrival[1]=940 < departure[0]=910? No, departure[0] leaves	1	1	0	1	Platforms: [Train at 900 departs]
3	arrival[1]=940 < departure[1]=1120? Yes, arrival comes	1	1	1	1	Platforms: [Train at 940 arrives]
4	arrival[2]=950 < departure[1]=1120? Yes, arrival comes	2	1	2	2	Platforms: [Trains at 940, 950]
5	arrival[3]=1100 < departure[1]=1120? Yes, arrival comes	3	1	3	3	Platforms: [Trains at 940, 950, 1100]
6	arrival[4]=1500 < departure[1]=1120? No, departure leaves	4	2	2	3	Platforms: [Trains at 950, 1100]
7	arrival[4]=1500 < departure[2]=1130? No, departure leaves	4	3	1	3	Platforms: [Train at 1100]
8	arrival[4]=1500 < departure[3]=1200? No, departure leaves	4	4	0	3	Platforms: []
9	arrival[4]=1500 < departure[4]=1900? Yes, arrival comes	4	4	1	3	Platforms: [Train at 1500]
10	arrival[5]=1800 < departure[4]=1900? Yes, arrival comes	5	4	2	3	Platforms: [Trains at 1500, 1800]
11	No more arrivals, process remaining departures	6	4	2	3	Platforms: [Trains at 1500, 1800]
12	departure[4]=1900 leaves	6	5	1	3	Platforms: [Train at 1800]
13	departure[5]=2000 leaves	6	6	0	3	Platforms: []

💡 All trains processed, max platforms needed is 3

Variable Tracker

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

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

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

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 5, how many platforms are currently needed?

A 1

B 2

C 3

D 0

💡 Hint

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

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

A Step 3

B Step 5

C Step 6

D Step 4

💡 Hint

Look for the first time 'Current Platforms' equals 3 in execution_table.

If the arrival time at index 2 changed from 950 to 1210, what would happen to max platforms?

A It would increase

B It would stay the same

C It would decrease

D It would become zero

💡 Hint

Consider how later arrival affects overlap and check variable_tracker for platform counts.

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 needed during traversal.
- Result is max platforms to avoid waiting.

Full Transcript

To find the minimum number of platforms needed for trains, first sort the arrival and departure times. Then use two pointers to compare the next arrival and departure. If the next train arrives before the earliest departure, increase the platform count. If a train departs before the next arrival, decrease the platform count. Keep track of the maximum platforms needed at any time. This ensures no train waits for a platform. The example shows step-by-step how platforms increase and decrease as trains arrive and depart, with the maximum platforms needed being 3.

Practice

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

easy

A. The total time trains spend at the station

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

C. The maximum speed of any train

D. The total number of trains arriving in a day

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 B

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 speed or travel time

2. Which Rust data structure is best suited to keep track of train departure times when solving the Minimum Number of Platforms problem?

easy

A. BinaryHeap (priority queue)

B. VecDeque (double-ended queue)

C. HashMap (key-value store)

D. LinkedList

Solution

1. Step 1: Identify the need for ordering

   We need to quickly access the earliest departure time to compare with arrivals.

2. Step 2: Choose a data structure that supports this

   A BinaryHeap (priority queue) efficiently gives the smallest or largest element, perfect for earliest departure.

3. Final Answer:

   BinaryHeap (priority queue) -> Option A

4. Quick Check:

   Priority queue = earliest departure access [OK]

Hint: Use priority queue to track earliest departure times [OK]

Common Mistakes:

• Using HashMap which doesn't keep order
• Using LinkedList which is inefficient for min extraction
• Using VecDeque which is FIFO, not sorted

3. What is the output of the following Rust code snippet that calculates minimum platforms?

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

// After sorting both vectors
// Calculate minimum platforms needed
// Output the result

// Assume correct implementation of algorithm
println!("{}", min_platforms(arrivals, departures));

medium

A. 3

B. 2

C. 4

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: Count overlapping trains

   At 1100 arrival, trains at station are 3 (940-1200, 950-1120, 1100-1130 overlap). So minimum platforms = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max overlap = 3 platforms [OK]

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

Common Mistakes:

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

4. Identify the bug in this Rust function snippet for minimum platforms calculation:

fn min_platforms(arrivals: Vec<i32>, departures: Vec<i32>) -> i32 {
    let mut arr = arrivals.clone();
    let mut dep = departures.clone();
    arr.sort();
    dep.sort();
    let mut platform_needed = 1;
    let mut max_platforms = 1;
    let mut i = 1;
    let mut j = 0;
    while i < arr.len() && j < dep.len() {
        if arr[i] <= dep[j] {
            platform_needed += 1;
            i += 1;
        } else {
            platform_needed -= 1;
            j += 1;
        }
        if platform_needed > max_platforms {
            max_platforms = platform_needed;
        }
    }
    max_platforms
}

medium

A. Using clone() causes runtime error

B. Sorting departures is unnecessary

C. Starting i from 1 skips first arrival comparison

D. The loop condition should be OR instead of AND

Solution

1. Step 1: Check loop initialization

   Variable i starts at 1, skipping the first arrival time comparison which can cause incorrect platform count.

2. Step 2: Understand impact of skipping first arrival

   Missing the first arrival means initial platform count may be wrong, leading to incorrect max platforms.

3. Final Answer:

   Starting i from 1 skips first arrival comparison -> Option C

4. Quick Check:

   Indexing from 1 skips first train [OK]

Hint: Start indices at 0 to include all trains [OK]

Common Mistakes:

• Ignoring index start positions
• Thinking sorting is unnecessary
• Confusing clone() with error cause

5. Given arrival times [100, 140, 150, 200, 215, 400] and departure times [110, 300, 220, 230, 315, 600], what is the minimum number of platforms needed? Explain why this number is required.

hard

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Sort arrival and departure times

   Arrivals sorted: [100, 140, 150, 200, 215, 400] Departures sorted: [110, 220, 230, 300, 315, 600]

2. Step 2: Count overlapping trains step-by-step

   At 215 arrival, trains at station: 140-300, 150-220, 200-230, 215-315 (4) overlap. Maximum overlap is 4, so 4 platforms needed.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Max overlap = 4 platforms [OK]

Hint: Find max overlapping intervals for platform count [OK]

Common Mistakes:

• Not sorting times before counting
• Miscounting overlaps at arrival times
• Assuming platforms equal total trains