Merge Overlapping Intervals in DSA Rust

Mental Model

We combine intervals that overlap into one bigger interval so no two intervals cover the same range twice.

Analogy: Imagine you have several time blocks booked on a calendar. If some blocks overlap, you merge them into one longer block so you don't double count the time.

Intervals before merge:
[1,3] -> [2,6] -> [8,10] -> [15,18]

Intervals after merge:
[1,6] -> [8,10] -> [15,18]

Dry Run Walkthrough

Input: intervals: [[1,3], [2,6], [8,10], [15,18]]

Goal: Merge all overlapping intervals into combined intervals without overlaps

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18]

Why: Sorting helps us check overlaps in order

Step 2: Start merged list with first interval [1,3]

[1,3]

Why: We need a base to compare next intervals

Step 3: Check next interval [2,6], it overlaps with [1,3], merge to [1,6]

[1,6]

Why: Intervals overlap if next start ≤ current end, so merge by extending end

Step 4: Check next interval [8,10], no overlap with [1,6], add as new interval

[1,6] -> [8,10]

Why: No overlap means separate interval

Step 5: Check next interval [15,18], no overlap with [8,10], add as new interval

[1,6] -> [8,10] -> [15,18]

Why: No overlap means separate interval

Result:

[1,6] -> [8,10] -> [15,18]

Annotated Code

DSA Rust

fn merge_intervals(mut intervals: Vec<[i32; 2]>) -> Vec<[i32; 2]> {
    if intervals.is_empty() {
        return vec![];
    }
    intervals.sort_by_key(|k| k[0]); // sort intervals by start
    let mut merged = Vec::new();
    merged.push(intervals[0]); // start with first interval
    for i in 1..intervals.len() {
        let last = merged.last_mut().unwrap();
        if intervals[i][0] <= last[1] {
            // overlap, merge by extending end
            if intervals[i][1] > last[1] {
                last[1] = intervals[i][1];
            }
        } else {
            // no overlap, add new interval
            merged.push(intervals[i]);
        }
    }
    merged
}

fn main() {
    let intervals = vec![[1,3], [2,6], [8,10], [15,18]];
    let merged = merge_intervals(intervals);
    for interval in merged {
        println!("[{},{}]", interval[0], interval[1]);
    }
}

intervals.sort_by_key(|k| k[0]); // sort intervals by start

sort intervals by their start time to process in order

merged.push(intervals[0]); // start with first interval

initialize merged list with first interval

for i in 1..intervals.len() {

iterate over remaining intervals

let last = merged.last_mut().unwrap();

get last merged interval to compare with current

if intervals[i][0] <= last[1] {

check if current interval overlaps with last merged

if intervals[i][1] > last[1] { last[1] = intervals[i][1]; }

extend end of last merged interval if current ends later

} else { merged.push(intervals[i]); }

no overlap, add current interval as new merged interval

Output

[1,6]

[8,10]

[15,18]

Complexity Analysis

Time: O(n log n) because sorting intervals takes O(n log n) and merging takes O(n)

Space: O(n) because in worst case no intervals overlap and merged list stores all intervals

vs Alternative: Naive approach checks every pair for overlap O(n^2), this approach is faster due to sorting and single pass merge

Edge Cases

empty intervals list

returns empty list immediately

DSA Rust

if intervals.is_empty() { return vec![]; }

all intervals non-overlapping

merged list is same as input after sorting

DSA Rust

else { merged.push(intervals[i]); }

all intervals overlapping into one

merged list contains single interval covering all

DSA Rust

if intervals[i][0] <= last[1] { if intervals[i][1] > last[1] { last[1] = intervals[i][1]; } }

When to Use This Pattern

When you see a problem asking to combine or simplify overlapping ranges, reach for the merge intervals pattern because sorting and merging in one pass solves it efficiently.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Sort intervals by start time first to ensure correct merging order

Mistake: Not updating the end of merged interval when current interval extends it
Fix: Update the end of last merged interval if current interval ends later

Mistake: Adding overlapping intervals separately instead of merging
Fix: Check overlap condition and merge intervals instead of adding duplicates

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you need to simplify or combine overlapping ranges into minimal intervals.

Sort intervals by start time, then merge overlapping intervals by extending the end.

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