Merge Overlapping Intervals in DSA Rust - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Start with first interval

↓

For each next interval

↓

Check overlap with last merged

↓

Merge intervals

↓

Repeat

↓

Done

Sort intervals by start time, then merge overlapping ones by comparing current interval with last merged.

Execution Sample

DSA Rust

fn merge_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_by_key(|k| k.0);
    let mut merged = Vec::new();
    for interval in intervals {
        if let Some(last) = merged.last_mut() {
            if interval.0 <= last.1 {
                last.1 = last.1.max(interval.1);
                continue;
            }
        }
        merged.push(interval);
    }
    merged
}

Sort intervals, then merge overlapping intervals into a new list.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged Intervals State
1	Sort intervals	[(1,3), (2,6), (8,10), (15,18)]	[]	Sorted by start	[]
2	Start merging	(1,3)	None	Add (1,3)	[(1,3)]
3	Check overlap	(2,6)	(1,3)	2 <= 3 overlap, merge	[(1,6)]
4	Check overlap	(8,10)	(1,6)	8 > 6 no overlap, add	[(1,6), (8,10)]
5	Check overlap	(15,18)	(8,10)	15 > 10 no overlap, add	[(1,6), (8,10), (15,18)]
6	Done	None	(15,18)	All intervals processed	[(1,6), (8,10), (15,18)]

💡 All intervals processed, merged list contains non-overlapping intervals.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[(1,3), (2,6), (8,10), (15,18)]	[(1,3), (2,6), (8,10), (15,18)]	[(1,3), (2,6), (8,10), (15,18)]	[(1,3), (2,6), (8,10), (15,18)]	[(1,3), (2,6), (8,10), (15,18)]	[(1,3), (2,6), (8,10), (15,18)]
merged	[]	[(1,3)]	[(1,6)]	[(1,6), (8,10)]	[(1,6), (8,10), (15,18)]	[(1,6), (8,10), (15,18)]
last	None	(1,3)	(1,6)	(8,10)	(15,18)	(15,18)
current	None	(1,3)	(2,6)	(8,10)	(15,18)	None

Key Moments - 3 Insights

Why do we merge intervals only when current start <= last merged end?

Because intervals overlap only if the current interval starts before or exactly when the last merged interval ends. See step 3 in execution_table where 2 <= 3 triggers merge.

Why do we update last merged interval's end with max of both ends?

To cover the full range of overlapping intervals. In step 3, last merged end 3 is updated to max(3,6)=6 to include the bigger interval.

What happens if intervals are not sorted before merging?

Merging fails because intervals may not be in order, causing missed overlaps. Sorting in step 1 ensures correct merging order.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the merged intervals state?

A [(1,6)]

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

C [(2,6)]

D [(1,3)]

💡 Hint

Check the 'Merged Intervals State' column at step 3 in execution_table.

At which step does the condition for no overlap occur?

A Step 3

B Step 2

C Step 4

D Step 1

💡 Hint

Look for where current interval start is greater than last merged end in execution_table.

If the intervals were not sorted, what would likely happen to the merged intervals?

A They would be merged correctly anyway

B Some overlapping intervals might not merge

C The merged list would be empty

D All intervals would merge into one

💡 Hint

Refer to key_moments about the importance of sorting before merging.

Concept Snapshot

Merge Overlapping Intervals:
- Sort intervals by start time
- Iterate intervals, compare current start with last merged end
- If overlap, merge by updating end to max
- Else, add current interval to merged list
- Result: list of non-overlapping intervals covering all input ranges

Full Transcript

This visualization shows how to merge overlapping intervals step-by-step. First, intervals are sorted by their start times. Then, starting from the first interval, each next interval is checked for overlap with the last merged interval. If the current interval starts before or at the end of the last merged interval, they overlap and are merged by extending the end time. Otherwise, the current interval is added as a new separate interval. This process continues until all intervals are processed, resulting in a list of merged, non-overlapping intervals.

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