Merge Overlapping Intervals in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging intervals with overlapping pairs

What is the output of the following Rust code that merges overlapping intervals?

DSA Rust

fn merge_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        return vec![];
    }
    intervals.sort_by_key(|k| k.0);
    let mut merged = vec![intervals[0]];
    for current in intervals.into_iter().skip(1) {
        let last = merged.last_mut().unwrap();
        if current.0 <= last.1 {
            last.1 = last.1.max(current.1);
        } else {
            merged.push(current);
        }
    }
    merged
}

fn main() {
    let intervals = vec![(1, 4), (2, 5), (7, 9), (8, 10)];
    let result = merge_intervals(intervals);
    println!("{:?}", result);
}

A [(1, 4), (7, 10)]

B [(1, 4), (2, 5), (7, 9), (8, 10)]

C [(1, 5), (7, 9), (8, 10)]

D [(1, 5), (7, 10)]

💡 Hint

Think about sorting intervals by start time and merging when they overlap.

The code sorts intervals by their start value. Then it merges intervals that overlap by extending the end of the last merged interval.

Intervals (1,4) and (2,5) overlap and merge into (1,5). Intervals (7,9) and (8,10) overlap and merge into (7,10).

❓ Predict Output

intermediate

Result after merging intervals with no overlaps

What is the output of this Rust code merging intervals that do not overlap?

DSA Rust

fn merge_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        return vec![];
    }
    intervals.sort_by_key(|k| k.0);
    let mut merged = vec![intervals[0]];
    for current in intervals.into_iter().skip(1) {
        let last = merged.last_mut().unwrap();
        if current.0 <= last.1 {
            last.1 = last.1.max(current.1);
        } else {
            merged.push(current);
        }
    }
    merged
}

fn main() {
    let intervals = vec![(1, 2), (3, 4), (5, 6)];
    let result = merge_intervals(intervals);
    println!("{:?}", result);
}

A [(1, 6)]

B [(1, 4), (5, 6)]

C [(1, 2), (3, 4), (5, 6)]

D [(1, 2), (3, 6)]

💡 Hint

No intervals overlap, so the output should be the same as input but sorted.

Since none of the intervals overlap, the merged list is the same as the sorted input intervals.

🔧 Debug

advanced

Identify the error in interval merging code

What error will this Rust code produce when merging intervals?

DSA Rust

fn merge_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_by_key(|k| k.0);
    let mut merged = vec![];
    for current in intervals {
        if merged.is_empty() || current.0 > merged.last().unwrap().1 {
            merged.push(current);
        } else {
            merged.last_mut().unwrap().1 = current.1.max(merged.last().unwrap().1);
        }
    }
    merged
}

fn main() {
    let intervals = vec![(1, 3), (2, 6), (8, 10)];
    let result = merge_intervals(intervals);
    println!("{:?}", result);
}

A The code compiles and outputs [(1, 6), (8, 10)]

B The code compiles but incorrectly updates the start of last interval causing wrong merge

C The code compiles but outputs [(1, 3), (2, 6), (8, 10)]

D The code compiles but outputs [(2, 6), (8, 10)]

💡 Hint

Check which part of the interval is updated during merging.

The code incorrectly updates the start of the last merged interval instead of the end. This causes wrong merging results.

🧠 Conceptual

advanced

Minimum number of intervals after merging

Given intervals [(1, 10), (2, 3), (4, 5), (6, 7), (8, 9)], what is the minimum number of intervals after merging all overlapping intervals?

A 1

B 2

C 5

D 3

💡 Hint

Check if smaller intervals are fully inside the largest interval.

All smaller intervals are inside (1, 10), so after merging, only one interval remains.

🚀 Application

expert

Merging intervals with large input and edge cases

You have a list of intervals where some intervals are single points like (5,5). After merging, what will be the output for the input intervals [(1, 3), (2, 6), (8, 8), (8, 10), (15, 18), (17, 17)]?

A [(1, 6), (8, 10), (15, 18)]

B [(1, 6), (8, 8), (8, 10), (15, 18), (17, 17)]

C [(1, 6), (8, 10), (15, 17)]

D [(1, 6), (8, 10), (15, 18), (17, 17)]

💡 Hint

Single point intervals merge if they overlap or touch other intervals.

Intervals (8,8) and (8,10) merge into (8,10). Intervals (15,18) and (17,17) overlap so they merge into (15,18). The first two intervals merge into (1,6).

Practice

1. What is the main goal when merging overlapping intervals in a list like [[1,3],[2,6],[8,10]]?

easy

A. Remove all intervals that overlap

B. Sort intervals by their end values only

C. Combine intervals that overlap into one continuous interval

D. Split intervals into smaller parts

Solution

1. Step 1: Understand overlapping intervals

   Intervals overlap if one starts before the other ends. For example, [1,3] and [2,6] overlap.

2. Step 2: Merge overlapping intervals

   We combine overlapping intervals into one that covers both, like merging [1,3] and [2,6] into [1,6].

3. Final Answer:

   Combine intervals that overlap into one continuous interval -> Option C

4. Quick Check:

   Merging overlapping intervals means combining them [OK]

Hint: Merge intervals by combining overlapping ranges [OK]

Common Mistakes:

• Sorting only by end values misses correct merges
• Removing intervals instead of merging
• Splitting intervals unnecessarily

2. Which Rust code snippet correctly sorts a vector of intervals by their start value before merging?

easy

A. intervals.sort_by_key(|interval| interval[0]);

B. intervals.sort();

C. intervals.sort_by(|a, b| b[0].cmp(&a[0]));

D. intervals.sort_by_key(|interval| interval[1]);

Solution

1. Step 1: Identify sorting by start value

   We want to sort intervals by their first element (start), so we use sort_by_key with interval[0].

2. Step 2: Check sorting direction and key

   intervals.sort_by_key(|interval| interval[0]); sorts ascending by start, which is correct. intervals.sort_by(|a, b| b[0].cmp(&a[0])); sorts descending, which is wrong. intervals.sort_by_key(|interval| interval[1]); sorts by end, not start.

3. Final Answer:

   intervals.sort_by_key(|interval| interval[0]); -> Option A

4. Quick Check:

   Sort by start value using sort_by_key(interval[0]) [OK]

Hint: Use sort_by_key with interval[0] to sort by start [OK]

Common Mistakes:

• Sorting by end instead of start
• Sorting descending instead of ascending
• Using sort() without key for nested vectors

3. What is the output of this Rust code that merges overlapping intervals?

let mut intervals = vec![vec![1,4], vec![2,5], vec![7,9]];
intervals.sort_by_key(|x| x[0]);
let mut merged = vec![];
for interval in intervals {
    if merged.is_empty() || merged.last().unwrap()[1] < interval[0] {
        merged.push(interval);
    } else {
        let last = merged.last_mut().unwrap();
        last[1] = last[1].max(interval[1]);
    }
}
println!("{:?}", merged);

medium

A. [[2,5], [7,9]]

B. [[1,4], [2,5], [7,9]]

C. [[1,9]]

D. [[1,5], [7,9]]

Solution

1. Step 1: Sort intervals by start

   Sorted intervals: [[1,4], [2,5], [7,9]] (already sorted).

2. Step 2: Merge overlapping intervals

   [1,4] and [2,5] overlap, merged to [1,5]. [7,9] does not overlap, so added as is.

3. Final Answer:

   [[1,5], [7,9]] -> Option D

4. Quick Check:

   Merged intervals = [[1,5], [7,9]] [OK]

Hint: Merge intervals by extending end if overlapping [OK]

Common Mistakes:

• Not merging overlapping intervals
• Merging non-overlapping intervals
• Incorrectly updating interval ends

4. Identify the bug in this Rust code for merging intervals:

let mut intervals = vec![vec![1,3], vec![2,4], vec![5,7]];
intervals.sort_by_key(|x| x[1]);
let mut merged = vec![];
for interval in intervals {
    if merged.is_empty() || merged.last().unwrap()[1] < interval[0] {
        merged.push(interval);
    } else {
        let last = merged.last_mut().unwrap();
        last[1] = last[1].max(interval[1]);
    }
}
println!("{:?}", merged);

medium

A. Sorting by end value causes incorrect merging

B. Using last_mut() causes a runtime error

C. The vector intervals is not mutable

D. The condition to check overlap is reversed

Solution

1. Step 1: Check sorting key

   The code sorts intervals by their end value, but merging requires sorting by start value to process intervals in order.

2. Step 2: Effect of wrong sorting

   Sorting by end causes intervals to be processed out of order, leading to missed merges or incorrect merges.

3. Final Answer:

   Sorting by end value causes incorrect merging -> Option A

4. Quick Check:

   Sort by start, not end, for correct merging [OK]

Hint: Always sort intervals by start before merging [OK]

Common Mistakes:

• Sorting by end instead of start
• Misusing mutable references
• Incorrect overlap condition

5. Given a list of intervals [[1,3],[2,4],[5,7],[6,8],[9,10]], write a Rust function to merge all overlapping intervals and return the merged list. What is the correct merged output?

hard

A. [[1,3],[2,4],[5,7],[6,8],[9,10]]

B. [[1,4],[5,8],[9,10]]

C. [[1,8],[9,10]]

D. [[1,4],[5,7],[6,8],[9,10]]

Solution

1. Step 1: Sort intervals by start

   Sorted intervals: [[1,3],[2,4],[5,7],[6,8],[9,10]] (already sorted).

2. Step 2: Merge overlapping intervals step-by-step

   Merge [1,3] and [2,4] to [1,4]. Merge [5,7] and [6,8] to [5,8]. [9,10] stays separate.

3. Final Answer:

   [[1,4],[5,8],[9,10]] -> Option B

4. Quick Check:

   Merge intervals by extending ends where overlapping [OK]

Hint: Merge intervals by sorting and extending ends [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Merging non-overlapping intervals
• Incorrect final intervals after merge