Non Overlapping Intervals Minimum Removal in DSA Rust

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping the interval that ends earliest to leave room for others.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings without clashes, always pick the meeting that finishes earliest, then schedule the next meeting that starts after it ends.

Intervals: [1,3] -> [2,4] -> [3,5] -> [6,7]
Goal: Remove minimum intervals so none overlap.

Dry Run Walkthrough

Input: intervals: [[1,3], [2,4], [3,5], [6,7]]

Goal: Remove the fewest intervals so that no two intervals overlap

Step 1: Sort intervals by end time

[1,3] -> [2,4] -> [3,5] -> [6,7]

Why: Sorting by end time helps pick intervals that finish earliest first

Step 2: Keep first interval [1,3], set end = 3

[1,3] ↑ -> [2,4] -> [3,5] -> [6,7]

Why: Start with earliest finishing interval to maximize room for others

Step 3: Check [2,4]: start 2 < end 3 -> overlap, remove it

[1,3] ↑ -> [2,4](removed) -> [3,5] -> [6,7]

Why: Overlap means we must remove this interval

Step 4: Check [3,5]: start 3 >= end 3 -> keep it, update end = 5

[1,3] -> [3,5] ↑ -> [6,7]

Why: No overlap, so keep and update end to this interval's end

Step 5: Check [6,7]: start 6 >= end 5 -> keep it, update end = 7

[1,3] -> [3,5] -> [6,7] ↑

Why: No overlap, keep it

Result:

[1,3] -> [3,5] -> [6,7]
Minimum removals = 1

Annotated Code

DSA Rust

use std::cmp::Ordering;

#[derive(Debug, Clone)]
struct Interval {
    start: i32,
    end: i32,
}

impl Interval {
    fn new(start: i32, end: i32) -> Self {
        Interval { start, end }
    }
}

fn erase_overlap_intervals(intervals: &mut Vec<Interval>) -> i32 {
    if intervals.is_empty() {
        return 0;
    }
    // Sort intervals by their end time
    intervals.sort_by(|a, b| a.end.cmp(&b.end));

    let mut count = 0;
    let mut end = intervals[0].end;

    for i in 1..intervals.len() {
        if intervals[i].start < end {
            // Overlap detected, remove this interval
            count += 1;
        } else {
            // No overlap, update end to current interval's end
            end = intervals[i].end;
        }
    }
    count
}

fn main() {
    let mut intervals = vec![
        Interval::new(1, 3),
        Interval::new(2, 4),
        Interval::new(3, 5),
        Interval::new(6, 7),
    ];

    let removals = erase_overlap_intervals(&mut intervals);
    println!("Minimum removals = {}", removals);
}

intervals.sort_by(|a, b| a.end.cmp(&b.end));

Sort intervals by their end time to pick earliest finishing intervals first

let mut end = intervals[0].end;

Initialize end to the end of the first interval after sorting

if intervals[i].start < end { count += 1; } else { end = intervals[i].end; }

If current interval starts before end, it overlaps and must be removed; otherwise update end

Output

Minimum removals = 1

Complexity Analysis

Time: O(n log n) because we sort the intervals first, then do a single pass through them

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

vs Alternative: A naive approach checking all pairs for overlap is O(n^2), so sorting + greedy is much faster

Edge Cases

empty intervals list

returns 0 removals since no intervals exist

DSA Rust

if intervals.is_empty() { return 0; }

all intervals non-overlapping

returns 0 removals as no overlaps exist

DSA Rust

if intervals[i].start < end { count += 1; } else { end = intervals[i].end; }

all intervals overlapping

removes all but one interval, returns n-1

DSA Rust

if intervals[i].start < end { count += 1; } else { end = intervals[i].end; }

When to Use This Pattern

When asked to remove minimum intervals to avoid overlaps, reach for the greedy pattern that sorts by end time and picks earliest finishing intervals first.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to correctly apply the greedy approach

Mistake: Updating end pointer incorrectly when removing intervals
Fix: Only update end when keeping an interval, not when removing

Summary

Removes the fewest intervals so that no intervals overlap.

Use when you want to schedule intervals without conflicts by removing minimum intervals.

Always pick intervals that finish earliest to leave room for others.

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