Minimum Number of Platforms in DSA Rust - Build from Scratch

Minimum Number of Platforms

📖 Scenario: You are managing a small train station. You want to find out the minimum number of platforms needed so that no train has to wait.Each train has an arrival time and a departure time.

🎯 Goal: Build a Rust program that calculates the minimum number of platforms needed for the trains given their arrival and departure times.

📋 What You'll Learn

Create two vectors called arrivals and departures with exact train times

Create a variable called platforms_needed to track platforms required

Use a loop to find the minimum number of platforms needed

Print the final number of platforms needed

💡 Why This Matters

🌍 Real World

Train stations and airports use this logic to manage platforms and gates efficiently to avoid delays.

💼 Career

This problem teaches sorting and two-pointer techniques useful in scheduling, resource allocation, and event management software.

1

Create arrival and departure time vectors

Create a vector called arrivals with these exact values: 900, 940, 950, 1100, 1500, 1800. Also create a vector called departures with these exact values: 910, 1200, 1120, 1130, 1900, 2000.

DSA Rust

// Your code here

Hint

Use vec![...] to create vectors with the exact times.

2

Create variables for tracking platforms and indices

Create three variables: platforms_needed set to 1, max_platforms set to 1, and two indices i and j both set to 1 and 0 respectively.

DSA Rust

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

Hint

Use let mut to create variables that will change.

3

Calculate minimum platforms needed using a loop

Sort the arrivals and departures vectors. Then use a while loop with condition i < arrivals.len() && j < departures.len(). Inside the loop, if arrivals[i] <= departures[j], increment platforms_needed and i. Else, decrement platforms_needed and increment j. Update max_platforms to the maximum of itself and platforms_needed inside the loop.

DSA Rust

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

let mut platforms_needed = 1;
let mut max_platforms = 1;
let mut i = 1;
let mut j = 0;

// Your code here

Hint

Sorting helps to compare times in order. Use a while loop to check arrivals and departures.

4

Print the minimum number of platforms needed

Print the value of max_platforms using println!("{}", max_platforms).

DSA Rust

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

arrivals.sort();
departures.sort();

let mut platforms_needed = 1;
let mut max_platforms = 1;
let mut i = 1;
let mut j = 0;

while i  max_platforms {
        max_platforms = platforms_needed;
    }
}

// Your code here

Hint

Use println!("{}", max_platforms) to show the result.

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