Non Overlapping Intervals Minimum Removal in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following Rust code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA Rust

fn erase_overlap_intervals(intervals: &mut Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.1);
    let mut count = 0;
    let mut end = std::i32::MIN;
    for interval in intervals.iter() {
        if interval.0 >= end {
            end = interval.1;
        } else {
            count += 1;
        }
    }
    count
}

fn main() {
    let mut intervals = vec![(1,3), (2,4), (3,5), (6,7)];
    let result = erase_overlap_intervals(&mut intervals);
    println!("{}", result);
}

A 2

B 3

C 1

D 0

💡 Hint

Sort intervals by their end time and count how many overlap with the last chosen interval.

The code sorts intervals by their end time. It then iterates through them, counting how many intervals overlap with the previously chosen interval's end. The minimum removals needed is the count of overlapping intervals.

🧠 Conceptual

intermediate

Understanding the greedy choice in interval removal

Why does sorting intervals by their end time help in minimizing the number of intervals to remove to avoid overlaps?

A Because choosing intervals with earliest end time leaves more room for following intervals.

B Because sorting by start time always guarantees minimum removals.

C Because sorting by length of intervals ensures fewer overlaps.

D Because sorting by end time groups overlapping intervals together.

💡 Hint

Think about how choosing intervals that finish earlier affects the remaining intervals.

Choosing intervals with the earliest end time allows more intervals to fit after it without overlapping, minimizing removals.

🔧 Debug

advanced

Identify the bug in interval removal code

What error will the following Rust code produce when run, and why?

DSA Rust

fn erase_overlap_intervals(intervals: &mut Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.0);
    let mut count = 0;
    let mut end = std::i32::MIN;
    for interval in intervals.iter() {
        if interval.0 >= end {
            end = interval.1;
        } else {
            count += 1;
        }
    }
    count
}

fn main() {
    let mut intervals = vec![(1,5),(2,3),(3,4)];
    let result = erase_overlap_intervals(&mut intervals);
    println!("{}", result);
}

A The code returns 2, which is incorrect for minimum removals.

B The code panics at runtime due to index out of bounds.

C The code returns 1, which is the correct minimum removals.

D The code does not compile due to a syntax error.

💡 Hint

Check the sorting criteria and how it affects the greedy choice.

The code sorts intervals by start time instead of end time, which can cause incorrect counting of overlaps and thus wrong minimum removals.

❓ Predict Output

advanced

Output of minimum removals with nested intervals

What is the output of the following Rust code for intervals with nested overlaps?

DSA Rust

fn erase_overlap_intervals(intervals: &mut Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.1);
    let mut count = 0;
    let mut end = std::i32::MIN;
    for interval in intervals.iter() {
        if interval.0 >= end {
            end = interval.1;
        } else {
            count += 1;
        }
    }
    count
}

fn main() {
    let mut intervals = vec![(1,10), (2,3), (4,5), (6,7), (8,9)];
    let result = erase_overlap_intervals(&mut intervals);
    println!("{}", result);
}

A 3

B 0

C 4

D 1

💡 Hint

After sorting by end time, simulate the greedy selection process.

The code picks intervals with earliest end time first, which are the smaller nested intervals. The large interval (1,10) overlaps with all others, so it must be removed to avoid overlaps.

🧠 Conceptual

expert

Why greedy approach works for minimum interval removals

Which statement best explains why the greedy algorithm that sorts intervals by end time and removes overlapping intervals produces the minimum number of removals?

A Because sorting by start time and removing overlaps guarantees minimal removals in all cases.

B Because choosing intervals with earliest end time always leaves maximum space for future intervals, ensuring optimal selection.

C Because removing the longest intervals first reduces total overlaps and thus removals.

D Because the algorithm tries all combinations and picks the minimal removal set.

💡 Hint

Think about how the greedy choice leaves room for more intervals.

The greedy algorithm picks intervals that finish earliest, maximizing the number of intervals that can fit without overlap, thus minimizing removals.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To find the maximum number of overlapping intervals

B. To merge all intervals into one big interval

C. To remove the minimum number of intervals so that the remaining intervals do not overlap

D. To sort intervals by their start time

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove as few intervals as possible so that no two intervals overlap.

2. Step 2: Clarify what non-overlapping means

   Non-overlapping means intervals do not share any common points except possibly touching ends.

3. Final Answer:

   To remove the minimum number of intervals so that the remaining intervals do not overlap -> Option C

4. Quick Check:

   Minimum removal = non-overlapping intervals [OK]

Hint: Focus on removing intervals, not merging or counting overlaps [OK]

Common Mistakes:

• Thinking the goal is to merge intervals
• Confusing maximum overlap with minimum removal
• Sorting intervals without removing any

2. Which Rust code snippet correctly declares a vector of intervals as tuples for this problem?

easy

A. let intervals = vec![[1, 3], [2, 4], [3, 5]];

B. let intervals = [(1, 3), (2, 4), (3, 5)];

C. let intervals = vec!{(1, 3), (2, 4), (3, 5)};

D. let intervals = vec![(1, 3), (2, 4), (3, 5)];

Solution

1. Step 1: Identify correct vector syntax in Rust

   Vectors use vec![] macro with parentheses for tuples.

2. Step 2: Check tuple and vector syntax

   let intervals = vec![(1, 3), (2, 4), (3, 5)]; uses vec![(1, 3), (2, 4), (3, 5)] which is correct for vector of tuples.

3. Final Answer:

   let intervals = vec![(1, 3), (2, 4), (3, 5)]; -> Option D

4. Quick Check:

   vec! macro + tuples = correct syntax [OK]

Hint: Use vec![] with parentheses for tuples, not brackets or braces [OK]

Common Mistakes:

• Using square brackets for tuples
• Using braces {} instead of brackets [] for vec!
• Declaring array without vec! macro

3. What is the output of the following Rust code that finds the minimum number of intervals to remove?

fn erase_overlap_intervals(mut intervals: Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.1);
    let mut count = 0;
    let mut end = std::i32::MIN;
    for interval in intervals {
        if interval.0 >= end {
            end = interval.1;
        } else {
            count += 1;
        }
    }
    count
}

fn main() {
    let intervals = vec![(1, 2), (2, 3), (3, 4), (1, 3)];
    println!("{}", erase_overlap_intervals(intervals));
}

medium

A. 0

B. 1

C. 3

D. 2

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: (1,2), (2,3), (1,3), (3,4)

2. Step 2: Iterate and count overlaps

   Check intervals: - (1,2): end = 2, count=0 - (2,3): start 2 >= end 2, end=3, count=0 - (1,3): start 1 < end 3, count=1 (remove this) - (3,4): start 3 >= end 3, end=4, count=1

3. Final Answer:

   1 -> Option B

4. Quick Check:

   One interval removed to avoid overlap [OK]

Hint: Sort by end time, count intervals starting before last end [OK]

Common Mistakes:

• Not sorting intervals by end time
• Counting intervals incorrectly when start equals end
• Confusing count of removals with count of intervals

4. Identify the bug in this Rust function for minimum interval removal:

fn erase_overlap_intervals(mut intervals: Vec<(i32, i32)>) -> i32 {
    intervals.sort_by_key(|k| k.0);
    let mut count = 0;
    let mut end = std::i32::MIN;
    for interval in intervals {
        if interval.0 >= end {
            end = interval.1;
        } else {
            count += 1;
        }
    }
    count
}

medium

A. Sorting intervals by start time instead of end time causes incorrect removal count

B. Using std::i32::MIN for end causes overflow

C. The count variable should be initialized to 1

D. The function should return a boolean instead of i32

Solution

1. Step 1: Check sorting criteria

   The function sorts intervals by start time, but correct approach is sorting by end time to minimize removals.

2. Step 2: Understand impact of sorting

   Sorting by start time can cause wrong intervals to be kept, increasing removals incorrectly.

3. Final Answer:

   Sorting intervals by start time instead of end time causes incorrect removal count -> Option A

4. Quick Check:

   Sort by end time, not start time [OK]

Hint: Always sort intervals by their end time for this problem [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Misinitializing end variable
• Returning wrong data type

5. Given intervals [(1, 5), (2, 3), (4, 6), (7, 8), (5, 7)], what is the minimum number of intervals to remove to make the rest non-overlapping?

hard

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: (2,3), (1,5), (4,6), (5,7), (7,8)

2. Step 2: Greedily select non-overlapping intervals and count removals

   Initialize end = MIN, count = 0
   • (2,3): 2 >= MIN, keep, end=3
   • (1,5): 1 < 3, remove, count=1
   • (4,6): 4 >= 3, keep, end=6
   • (5,7): 5 < 6, remove, count=2
   • (7,8): 7 >= 6, keep, end=8
   Total removals: 2. This greedy approach by earliest end time yields the minimum.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Minimum removals = 2 [OK]

Hint: Sort by end, greedily keep intervals, count removals [OK]

Common Mistakes:

• Assuming zero removals without checking overlaps
• Not sorting intervals before processing
• Counting removals incorrectly when intervals touch