Merge Overlapping Intervals in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Merge Overlapping Intervals algorithm?

To combine all intervals that overlap into a single continuous interval, so the final list has no overlapping intervals.

beginner

Why do we sort intervals by their start time before merging?

Sorting helps to easily find overlapping intervals by comparing each interval only with the previous merged interval.

beginner

In Rust, which data structure is commonly used to represent intervals for merging?

A vector of tuples or structs, where each tuple or struct holds the start and end values of an interval, e.g., Vec<(i32, i32)>.

beginner

What happens if two intervals do not overlap during the merge process?

The current interval is added as a new interval to the result list because it does not merge with the previous one.

intermediate

How do you update the merged interval when two intervals overlap?

You update the end of the merged interval to the maximum end value between the two overlapping intervals.

What is the first step in merging overlapping intervals?

A Sort intervals by start time

B Sort intervals by end time

C Reverse the intervals

D Remove all intervals

Sorting intervals by their start time helps to easily find overlaps by comparing consecutive intervals.

If intervals (1, 4) and (3, 5) overlap, what is the merged interval?

A (1, 5)

B (3, 5)

C (1, 3)

D (4, 5)

The merged interval covers from the earliest start (1) to the latest end (5).

Which Rust collection type is best for storing intervals to merge?

A HashMap<i32, i32>

B Vec<(i32, i32)>

C LinkedList<i32>

D HashSet<i32>

A vector of tuples is simple and efficient for storing intervals with start and end values.

What do you do when the current interval does NOT overlap with the last merged interval?

A Merge them anyway

B Discard the current interval

C Replace the last merged interval

D Add the current interval as a new interval

Non-overlapping intervals are kept separate and added to the result list.

What is the time complexity of the Merge Overlapping Intervals algorithm?

A O(log n)

B O(n^2)

C O(n log n)

D O(n)

Sorting the intervals takes O(n log n), and merging takes O(n), so overall O(n log n).

Explain step-by-step how to merge overlapping intervals given a list of intervals.

Think about sorting first and then merging by comparing intervals one by one.

Describe how you would implement the Merge Overlapping Intervals algorithm in Rust.

Focus on Rust vector operations and sorting methods.

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