Minimum Number of Platforms in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the minimum number of platforms needed?

Given arrival and departure times of trains, what is the minimum number of platforms required so that no train waits?

DSA Rust

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

    let mut platform_needed = 0;
    let mut max_platforms = 0;
    let mut i: usize = 0;
    let mut j: usize = 0;

    while i < arrivals.len() && j < departures.len() {
        if arrivals[i] <= departures[j] {
            platform_needed += 1;
            max_platforms = max_platforms.max(platform_needed);
            i += 1;
        } else {
            platform_needed -= 1;
            j += 1;
        }
    }

    max_platforms
}

fn main() {
    let arrivals = vec![900, 940, 950, 1100, 1500, 1800];
    let departures = vec![910, 1200, 1120, 1130, 1900, 2000];
    println!("{}", min_platforms(&arrivals, &departures));
}

A 3

B 4

C 2

D 5

💡 Hint

Sort arrival and departure times and compare them to find overlaps.

The code sorts arrival and departure times, then uses two pointers to count how many trains are at the station simultaneously. The maximum count is the minimum number of platforms needed.

❓ Predict Output

intermediate

Output of platform calculation with overlapping trains

What will be the output of the following Rust code that calculates minimum platforms?

DSA Rust

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

    let mut platform_needed = 0;
    let mut max_platforms = 0;
    let mut i: usize = 0;
    let mut j: usize = 0;

    while i < arrivals.len() && j < departures.len() {
        if arrivals[i] < departures[j] {
            platform_needed += 1;
            max_platforms = max_platforms.max(platform_needed);
            i += 1;
        } else {
            platform_needed -= 1;
            j += 1;
        }
    }

    max_platforms
}

fn main() {
    let arrivals = vec![1000, 1010, 1025, 1030];
    let departures = vec![1015, 1020, 1035, 1040];
    println!("{}", min_platforms(&arrivals, &departures));
}

A 3

B 2

C 4

D 1

💡 Hint

Check how many trains overlap at the same time.

The maximum number of trains overlapping is 2, so 2 platforms are needed.

🔧 Debug

advanced

Why does this Rust code panic at runtime?

The following Rust code panics with an index out of bounds error. Why does this happen?

DSA Rust

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

    let mut platform_needed = 0;
    let mut max_platforms = 0;
    let mut i: usize = 0;
    let mut j: usize = 0;

    while i <= arrivals.len() && j <= departures.len() {
        if arrivals[i] <= departures[j] {
            platform_needed += 1;
            max_platforms = max_platforms.max(platform_needed);
            i += 1;
        } else {
            platform_needed -= 1;
            j += 1;
        }
    }

    max_platforms
}

fn main() {
    let arrivals = vec![900, 940, 950];
    let departures = vec![910, 1200, 1120];
    println!("{}", min_platforms(&arrivals, &departures));
}

A The platform_needed variable is not initialized properly, causing panic.

B The arrivals and departures vectors are not sorted, causing panic.

C The while loop condition allows i and j to equal the length, causing out of bounds access.

D The function returns before completing the loop, causing panic.

💡 Hint

Check the loop condition and how indices are used inside the loop.

The loop condition uses <= which allows i or j to become equal to the length of the arrays, causing out of bounds access when indexing.

🧠 Conceptual

advanced

Why sorting arrival and departure times is essential?

Why do we sort the arrival and departure times separately when calculating the minimum number of platforms?

A To process events in chronological order and correctly count overlapping trains.

B To group all arrivals before departures for easier counting.

C To ensure the trains are processed in the order they appear in input.

D To reduce the time complexity to O(n) without sorting.

💡 Hint

Think about how sorting helps in comparing arrival and departure events.

Sorting allows us to process arrival and departure events in order, so we can track how many trains are at the station at any time.

🚀 Application

expert

Calculate minimum platforms for large input efficiently

You have 1 million trains with random arrival and departure times. Which approach is best to calculate minimum platforms efficiently?

A Use a hash map to count trains at each time without sorting.

B Use nested loops to compare each train with every other train in O(n^2) time.

C Sort trains by arrival time only and count overlaps without considering departures.

D Sort arrivals and departures separately, then use two pointers to find overlaps in O(n log n) time.

💡 Hint

Consider time complexity and scalability for large inputs.

Sorting arrivals and departures and using two pointers is efficient and scalable for large inputs, running in O(n log n) time.

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