Minimum Number of Platforms in DSA Rust

Mental Model

We want to find the smallest number of train platforms needed so that 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 waits for a spot.

Time line ->
Arrivals:  |---|     |----|   |--|
Departures:    |----|    |---|    |--|
Platforms needed:  ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑

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 that no train waits.

Step 1: Sort arrivals and departures separately

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 process events in chronological order.

Step 2: Initialize pointers i=0 (arrivals), j=0 (departures), platforms=0, max_platforms=0

i=0, j=0, platforms=0, max_platforms=0

Why: We track how many trains are currently at the station.

Step 3: Compare arrival[0]=9:00 with departure[0]=9:10; arrival earlier, so platforms++

platforms=1, max_platforms=1, i=1, j=0

Why: A train arrives before any departs, so we need a platform.

Step 4: Compare arrival[1]=9:40 with departure[0]=9:10; departure earlier, so platforms--

platforms=0, max_platforms=1, i=1, j=1

Why: A train departs freeing a platform before next arrival.

Step 5: Compare arrival[1]=9:40 with departure[1]=11:20; arrival earlier, so platforms++

platforms=1, max_platforms=1, i=2, j=1

Why: Train arrives before next departure, need platform.

Step 6: Compare arrival[2]=9:50 with departure[1]=11:20; arrival earlier, so platforms++

platforms=2, max_platforms=2, i=3, j=1

Why: Another train arrives before departure, need another platform.

Step 7: Compare arrival[3]=11:00 with departure[1]=11:20; arrival earlier, so platforms++

platforms=3, max_platforms=3, i=4, j=1

Why: Third train arrives before departure, need third platform.

Step 8: Compare arrival[4]=15:00 with departure[1]=11:20; departure earlier, so platforms--

platforms=2, max_platforms=3, i=4, j=2

Why: Train departs freeing a platform.

Step 9: Compare arrival[4]=15:00 with departure[2]=11:30; departure earlier, so platforms--

platforms=1, max_platforms=3, i=4, j=3

Why: Another train departs freeing a platform.

Step 10: Compare arrival[4]=15:00 with departure[3]=12:00; departure earlier, so platforms--

platforms=0, max_platforms=3, i=4, j=4

Why: Another train departs freeing a platform.

Step 11: Compare arrival[4]=15:00 with departure[4]=19:00; arrival earlier, so platforms++

platforms=1, max_platforms=3, i=5, j=4

Why: Train arrives before next departure, need platform.

Step 12: Compare arrival[5]=18:00 with departure[4]=19:00; arrival earlier, so platforms++

platforms=2, max_platforms=3, i=6, j=4

Why: Another train arrives before departure, need platform.

Step 13: No more arrivals; process remaining departures, platforms-- until zero

platforms=1 after departure[4], platforms=0 after departure[5]

Why: Trains depart freeing platforms.

Result:

Final max_platforms = 3
Minimum platforms needed: 3

Annotated Code

DSA Rust

use std::cmp::Ordering;

fn min_platforms(arrivals: &mut [i32], departures: &mut [i32]) -> i32 {
    arrivals.sort_unstable();
    departures.sort_unstable();

    let mut i = 0;
    let mut j = 0;
    let mut platforms = 0;
    let mut max_platforms = 0;

    while i < arrivals.len() && j < departures.len() {
        if arrivals[i] <= departures[j] {
            platforms += 1; // train arrives, need platform
            if platforms > max_platforms {
                max_platforms = platforms; // update max
            }
            i += 1; // move to next arrival
        } else {
            platforms -= 1; // train departs, free platform
            j += 1; // move to next departure
        }
    }

    max_platforms
}

fn main() {
    // Times converted to minutes after midnight for simplicity
    let mut arrivals = vec![540, 580, 590, 660, 900, 1080]; // 9:00,9:40,9:50,11:00,15:00,18:00
    let mut departures = vec![550, 690, 690, 720, 1140, 1200]; // 9:10,11:30,11:30,12:00,19:00,20:00

    let result = min_platforms(&mut arrivals, &mut departures);
    println!("Minimum platforms needed: {}", result);
}

arrivals.sort_unstable(); departures.sort_unstable();

Sort arrivals and departures to process events in order

if arrivals[i] <= departures[j] { platforms += 1; if platforms > max_platforms { max_platforms = platforms; } i += 1; }

If next event is arrival, increase platforms and update max if needed

else { platforms -= 1; j += 1; }

If next event is departure, decrease platforms

Output

Minimum platforms needed: 3

Complexity Analysis

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

Space: O(1) because sorting is done in place and only a few variables are used

vs Alternative: Naive approach checks every train against every other train, resulting in O(n^2) time, which is slower for large inputs

Edge Cases

No trains (empty arrays)

Returns 0 platforms needed

DSA Rust

while i < arrivals.len() && j < departures.len() {

All trains arrive and depart at the same time

Platforms needed equals number of trains

DSA Rust

if arrivals[i] <= departures[j] {

Trains with overlapping times but some arrive exactly when others depart

Counts arrival before departure, ensuring platform count is correct

DSA Rust

if arrivals[i] <= departures[j] {

When to Use This Pattern

When you see problems asking for minimum resources needed to handle overlapping intervals, reach for the two-pointer sorting pattern to count overlaps efficiently.

Common Mistakes

Mistake: Not sorting arrivals and departures separately before processing
Fix: Sort both arrays independently to process events in chronological order

Mistake: Using '<' instead of '<=' when comparing arrival and departure times
Fix: Use '<=' to count trains arriving exactly when another departs as needing a platform

Summary

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

Use when scheduling resources for overlapping time intervals like trains or meetings.

Sort arrivals and departures separately, then use two pointers to count overlaps.

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