Merge Overlapping Intervals in DSA Rust - Deep Dive

Overview - Merge Overlapping Intervals

What is it?

Merge Overlapping Intervals is a way to combine intervals that share some common part into one bigger interval. Imagine you have many time slots or ranges, and some of them overlap or touch each other. This method finds those overlaps and merges them so that you get a list of intervals without any overlaps.

Why it matters

Without merging overlapping intervals, you might count the same time or range multiple times, causing confusion or errors. For example, if you schedule meetings that overlap, you might think you have more free time than you actually do. Merging intervals helps simplify data and makes it easier to understand and use.

Where it fits

Before learning this, you should understand arrays or lists and how to sort them. After this, you can learn about interval trees or more complex scheduling algorithms that build on merging intervals.

Mental Model

Core Idea

Combine intervals that touch or overlap into one continuous interval to avoid counting the same part multiple times.

Think of it like...

Imagine you have several pieces of tape on a table, some overlapping. Instead of counting each piece separately, you press them together to form one longer tape without gaps or overlaps.

Intervals before merging:
[1, 3]  [2, 6]  [8, 10]  [15, 18]

Intervals after merging:
[1, 6]  [8, 10]  [15, 18]

Visual:
┌─────┐
  ┌─────────┐
          ┌─────┐
                 ┌───────┐

Becomes:
┌─────────────┐
          ┌─────┐
                 ┌───────┐

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: Intervals are pairs of numbers representing a start and end. Overlaps happen when intervals share some part.

An interval is like a segment on a number line, for example [1, 3] means from 1 to 3. Two intervals overlap if one starts before the other ends. For example, [1, 3] and [2, 4] overlap because 2 is between 1 and 3.

Result

You can tell if two intervals overlap by checking if the start of one is less than or equal to the end of the other.

Understanding what intervals and overlaps are is the base for merging them correctly.

2

Foundation

Sorting Intervals by Start Time

Concept: Sorting intervals by their start time helps to process them in order and easily find overlaps.

Given intervals like [8, 10], [1, 3], [2, 6], sort them by the first number: Sorted: [1, 3], [2, 6], [8, 10] This order helps to check overlaps by moving from left to right.

Result

Intervals are arranged so that each interval starts after or at the same time as the previous one.

Sorting simplifies the problem by making overlaps appear only between neighbors.

3

Intermediate

Merging Overlapping Intervals Step-by-Step

🤔Before reading on: do you think merging intervals requires checking all pairs or just neighbors? Commit to your answer.

Concept: You only need to compare each interval with the last merged interval to decide if they overlap.

Start with the first interval as merged. For each next interval: - If it starts before or at the end of the last merged interval, merge by extending the end if needed. - Otherwise, add it as a new merged interval. Example: Input: [1, 3], [2, 6], [8, 10] Process: - Start with [1, 3] - [2, 6] overlaps with [1, 3], merge to [1, 6] - [8, 10] does not overlap, add as is Result: [1, 6], [8, 10]

Result

A list of intervals with no overlaps, each representing a combined range.

Knowing you only need to compare with the last merged interval reduces complexity and makes the algorithm efficient.

4

Intermediate

Implementing Merge in Rust with Vectors

🤔Before reading on: do you think Rust's ownership rules make merging intervals harder or easier? Commit to your answer.

Concept: Use Rust vectors to store intervals and carefully handle ownership and mutability while merging.

Define intervals as tuples (start, end). Sort the vector by start. Use a mutable vector to store merged intervals. Iterate over sorted intervals, compare with last merged, and update or push accordingly. Example code snippet: let mut intervals = vec![(1,3), (2,6), (8,10)]; 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); } else { merged.push(interval); } } else { merged.push(interval); } }

Result

A Rust vector containing merged intervals without overlaps.

Understanding Rust's ownership and mutability is key to writing safe and efficient merging code.

5

Intermediate

Handling Edge Cases in Interval Merging

🤔Before reading on: do you think intervals that just touch (like [1,2] and [2,3]) should merge? Commit to your answer.

Concept: Decide if touching intervals count as overlapping and handle accordingly.

Intervals that touch at the boundary (end of one equals start of another) can be merged if the problem requires it. Adjust the condition from < to <= when checking overlap. Example: [1, 2] and [2, 3] merge to [1, 3] if touching counts. Otherwise, they stay separate.

Result

Merged intervals correctly reflect problem requirements about touching intervals.

Clarifying problem requirements about touching intervals prevents subtle bugs.

6

Advanced

Optimizing Merge for Large Data Sets

🤔Before reading on: do you think sorting is the biggest cost in merging intervals? Commit to your answer.

Concept: Sorting dominates time complexity; merging is linear after sorting. Use efficient sorting and data structures for large inputs.

The algorithm runs in O(n log n) due to sorting. Merging is O(n). For very large data, use efficient sorting algorithms and consider parallel sorting if available. Also, avoid unnecessary copying by using references or in-place updates in Rust.

Result

Merge runs efficiently even on large interval lists.

Knowing where time is spent helps focus optimization efforts on sorting, not merging.

7

Expert

Surprising Behavior with Unsorted or Nested Intervals

🤔Before reading on: do you think merging works correctly without sorting? Commit to your answer.

Concept: Merging without sorting can miss overlaps or produce incorrect results, especially with nested intervals.

If intervals are not sorted, merging by comparing only the last merged interval fails. For example: Input: [5, 10], [1, 6] Without sorting, start with [5, 10], then [1, 6] does not overlap with last merged [5, 10] because 1 < 5 but 6 < 10, so it is added separately. Correct merge after sorting: [1, 10] This shows sorting is essential for correctness.

Result

Incorrect merges or missed overlaps if sorting is skipped.

Understanding the necessity of sorting prevents subtle bugs and ensures correctness.

Under the Hood

The algorithm first sorts intervals by their start value. Then it iterates through them, keeping track of the last merged interval. If the current interval overlaps or touches the last merged one, it updates the end of the last merged interval to cover both. Otherwise, it adds the current interval as a new merged interval. This works because sorting guarantees that any overlap can only happen with the last merged interval.

Why designed this way?

Sorting before merging simplifies the problem from checking all pairs to checking only neighbors, reducing complexity from quadratic to linear after sorting. This design balances simplicity and efficiency. Alternatives like interval trees exist but are more complex and used for dynamic queries rather than one-time merges.

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

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

Merging process:
Start: merged = [1,3]
Compare [2,6]: overlaps with [1,3], merge to [1,6]
Compare [8,10]: no overlap, add [8,10]
Compare [15,18]: no overlap, add [15,18]

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

Myth Busters - 4 Common Misconceptions

Quick: do you think intervals must be sorted before merging? Commit yes or no.

Common Belief: You can merge intervals correctly without sorting them first.

Reality: Sorting is essential; without it, some overlaps will be missed or merged incorrectly.

Why it matters: Skipping sorting leads to wrong merged intervals, causing errors in scheduling or range calculations.

Quick: do you think intervals that only touch at endpoints should always merge? Commit yes or no.

Common Belief: Intervals that touch at endpoints are not overlapping and should stay separate.

Reality: Depending on the problem, touching intervals often count as overlapping and should be merged to avoid gaps.

Why it matters: Not merging touching intervals can cause incorrect counts of free or busy time.

Quick: do you think merging intervals changes the total length covered? Commit yes or no.

Common Belief: Merging intervals can increase or decrease the total length covered by intervals.

Reality: Merging intervals never changes the total covered length; it only removes overlaps to avoid double counting.

Why it matters: Misunderstanding this can lead to wrong assumptions about resource usage or availability.

Quick: do you think merging intervals is always the best approach for interval problems? Commit yes or no.

Common Belief: Merging intervals is the best solution for all interval-related problems.

Reality: Merging is useful for simplifying intervals but not always the right approach, especially when intervals need to be queried dynamically or kept separate.

Why it matters: Using merging blindly can cause loss of important interval details needed for other operations.

Expert Zone

1

Merging intervals in-place in Rust requires careful handling of mutable references to avoid borrowing conflicts.

2

The choice between merging touching intervals or not depends on problem semantics and can affect downstream logic significantly.

3

For very large datasets, stable sorting preserves original order of equal start times, which can be important for deterministic results.

When NOT to use

Do not use merging when you need to keep intervals separate for individual processing or when intervals are frequently updated and queried dynamically. Instead, use interval trees or segment trees for efficient dynamic interval queries.

Production Patterns

In real systems, merging intervals is used in calendar apps to show busy/free times, in network systems to combine IP ranges, and in booking systems to avoid double bookings. Often, merging is combined with interval trees for efficient updates and queries.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which manage intervals dynamically and answer overlap queries efficiently.

Calendar Scheduling

Application

Merging intervals directly applies to scheduling meetings by combining overlapping time slots to find free or busy periods.

Data Compression

Similar pattern

Merging intervals is like compressing data ranges to reduce redundancy, a concept used in data storage and transmission.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

let intervals = vec![(5, 10), (1, 6)];
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);
} else {
merged.push(interval);
}
} else {
merged.push(interval);
}
}
// Result is incorrect because intervals are unsorted

Correct approach:

let mut intervals = vec![(5, 10), (1, 6)];
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);
} else {
merged.push(interval);
}
} else {
merged.push(interval);
}
}
// Result is correct after sorting

Root cause:

Failing to sort intervals breaks the assumption that only the last merged interval needs checking.

#2 Treating touching intervals as non-overlapping when problem requires merging.

Wrong approach:

if interval.0 < last.1 {
last.1 = last.1.max(interval.1);
} else {
merged.push(interval);
}
// Does not merge intervals like [1,2] and [2,3]

Correct approach:

if interval.0 <= last.1 {
last.1 = last.1.max(interval.1);
} else {
merged.push(interval);
}
// Correctly merges touching intervals

Root cause:

Misunderstanding problem requirements about whether touching counts as overlap.

#3 Modifying intervals while iterating without careful reference handling in Rust.

Wrong approach:

for interval in intervals {
if merged.last().unwrap().1 < interval.0 {
merged.push(interval);
} else {
merged.last().unwrap().1 = interval.1; // error: cannot assign to borrowed content
}
}

Correct approach:

for interval in intervals {
if let Some(last) = merged.last_mut() {
if interval.0 <= last.1 {
last.1 = last.1.max(interval.1);
} else {
merged.push(interval);
}
} else {
merged.push(interval);
}
}

Root cause:

Not using mutable references correctly causes compile errors and logic bugs.

Key Takeaways

Merging overlapping intervals combines ranges that share common parts into one continuous range to avoid double counting.

Sorting intervals by their start time is essential before merging to ensure correctness and efficiency.

Only the last merged interval needs to be checked for overlap with the current interval, simplifying the process.

Handling edge cases like touching intervals depends on problem requirements and affects the merging condition.

In Rust, careful handling of mutable references and ownership is crucial for implementing merging safely and efficiently.

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