Minimum Number of Platforms in DSA Rust - Time & Space Complexity

Time Complexity: Minimum Number of Platforms

O(n log n)

Understanding Time Complexity

We want to find how fast we can determine the minimum number of train platforms needed so that no train waits.

How does the time to find this number grow as we add more trains?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn find_min_platforms(arrivals: &mut [i32], departures: &mut [i32]) -> i32 {
    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
}
    

This code finds the minimum number of platforms needed so that no train waits by sorting arrival and departure times and then scanning them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the arrival and departure arrays, and then a single while loop scanning both arrays.
• How many times: Sorting takes time depending on the number of trains (n), and the while loop runs at most 2n times combined.

How Execution Grows With Input

As the number of trains (n) increases, sorting takes more time, growing faster than just scanning.

Input Size (n)	Approx. Operations
10	About 10 log 10 (sorting) + 20 (scanning)
100	About 100 log 100 + 200
1000	About 1000 log 1000 + 2000

Pattern observation: Sorting dominates and grows a bit faster than linear, while scanning grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to find the minimum platforms grows a bit faster than the number of trains because of sorting, but scanning is just linear.

Common Mistake

[X] Wrong: "The scanning loop alone decides the time complexity, so it is O(n)."

[OK] Correct: Sorting the arrival and departure times takes more time than scanning, so it controls the overall speed.

Interview Connect

Understanding this problem helps you practice combining sorting and two-pointer scanning, a common pattern in real-world scheduling and resource allocation tasks.

Self-Check

"What if the arrival and departure arrays were already sorted? How would the time complexity change?"

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