Merge Overlapping Intervals in DSA C++ - 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 you get fewer, bigger 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, scheduling meetings or booking rooms would be messy if overlapping times are treated separately. Merging helps simplify data, making 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 advanced scheduling algorithms that handle dynamic intervals efficiently.

Mental Model

Core Idea

If two intervals overlap or touch, combine them into one continuous interval to avoid repetition.

Think of it like...

Imagine you have several pieces of tape on a table, some overlapping. Instead of many small pieces, you want to glue overlapping pieces together to make longer strips without gaps or overlaps.

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

Process:
Sort intervals by start time
Check each interval with the last merged one
If overlapping, merge by extending the end
Else, add as new interval

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

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: Learn what intervals are and how to tell if two intervals overlap.

An interval is a pair of numbers representing a start and end, like [1,3]. Two intervals overlap if one starts before the other ends and ends after the other starts. For example, [1,3] and [2,6] overlap because 2 is between 1 and 3.

Result

You can identify when two intervals share some common part.

Understanding what overlap means is the base for merging intervals correctly.

2

Foundation

Sorting Intervals by Start Time

Concept: Sort intervals so they are in order by their start values.

Given intervals like [8,10], [1,3], [2,6], sort them by their start number to get [1,3], [2,6], [8,10]. Sorting helps us check overlaps in a single pass 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 easier to find in one go.

3

Intermediate

Merging Overlapping Intervals Step-by-Step

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

Concept: After sorting, only adjacent intervals need to be checked for overlap to merge them.

Start with the first interval as merged. For each next interval, compare its start with the end of the last merged interval. If they overlap (start <= last end), merge by updating the end to the max of both ends. Otherwise, add the new interval as separate.

Result

A list of merged intervals with no overlaps, e.g. [1,6], [8,10], [15,18].

Knowing that only adjacent intervals need checking after sorting reduces complexity and makes the algorithm efficient.

4

Intermediate

Implementing Merge in C++ with Vectors

🤔Before reading on: do you think using extra space is necessary for merging intervals or can it be done in-place? Commit to your answer.

Concept: Use a vector to store merged intervals and iterate through sorted intervals to build it.

Sort intervals by start. Create an empty vector for merged intervals. For each interval: - If merged is empty or no overlap, push interval. - Else merge by updating last interval's end. Example code snippet: #include #include using namespace std; vector> mergeIntervals(vector>& intervals) { sort(intervals.begin(), intervals.end()); vector> merged; for (auto& interval : intervals) { if (merged.empty() || merged.back()[1] < interval[0]) { merged.push_back(interval); } else { merged.back()[1] = max(merged.back()[1], interval[1]); } } return merged; }

Result

A function that returns merged intervals correctly for any input.

Using a separate vector for merged intervals keeps the code clean and avoids modifying input during iteration.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: do you think intervals that just touch (end equals start) should merge? Commit to yes or no.

Concept: Decide if intervals that touch at endpoints should merge and handle accordingly.

If intervals like [1,3] and [3,5] are considered overlapping, merge them into [1,5]. If not, keep separate. Usually, touching intervals are merged by checking if current start <= last end. Adjust condition based on requirement.

Result

Merged intervals that correctly reflect the problem's definition of overlap.

Clarifying how to treat touching intervals prevents bugs and matches real-world needs.

6

Advanced

Optimizing Merge for Large Data Sets

🤔Before reading on: do you think sorting is the main bottleneck in merging intervals? Commit to yes or no.

Concept: Sorting dominates time complexity; merging is linear after sorting.

Sorting intervals takes O(n log n) time. Merging after sorting is O(n). For very large data, focus on efficient sorting algorithms or parallel sorting. Also, consider in-place merging if memory is limited.

Result

Understanding that merge step is efficient and sorting is the main cost.

Knowing where time is spent helps optimize or choose the right approach for big inputs.

7

Expert

Advanced Uses and Interval Trees

🤔Before reading on: do you think merge overlapping intervals can handle dynamic insertions efficiently? Commit to yes or no.

Concept: Static merging is simple, but dynamic interval management requires advanced data structures like interval trees.

Interval trees store intervals to quickly find overlaps and insert/delete intervals dynamically. They allow merging or querying overlaps without sorting every time. This is useful in real-time systems or databases.

Result

A deeper understanding that merging intervals is a static problem, and dynamic interval management needs more complex tools.

Recognizing the limits of simple merging prepares you for advanced interval handling in real applications.

Under the Hood

The algorithm first sorts intervals by their start value so that overlapping intervals come next to each other. Then it iterates once through the sorted list, comparing the current interval with the last merged interval. If they overlap, it updates the end of the last merged interval to cover both. This avoids checking all pairs, reducing complexity from quadratic to linear after sorting.

Why designed this way?

Sorting first was chosen because it orders intervals to make overlap detection simple and efficient. Alternatives like checking every pair would be too slow. The design balances simplicity and performance, making it practical for many applications.

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

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

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

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

Myth Busters - 4 Common Misconceptions

Quick: Do you think intervals that only touch at endpoints should always be merged? Commit to yes or no.

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

Reality: Usually, touching intervals are considered overlapping and merged to form a continuous interval.

Why it matters: Not merging touching intervals can cause unnecessary fragmentation and incorrect results in scheduling or range queries.

Quick: Do you think sorting intervals by end time instead of start time works for merging? Commit to yes or no.

Common Belief: Sorting by end time is enough to merge intervals correctly.

Reality: Sorting by start time is necessary because merging depends on the order intervals begin, not just when they end.

Why it matters: Sorting by end time can miss overlaps and produce incorrect merges.

Quick: Do you think merging intervals can be done without sorting? Commit to yes or no.

Common Belief: You can merge intervals by checking overlaps in any order without sorting first.

Reality: Without sorting, you must check all pairs, which is inefficient and complex. Sorting simplifies the process to a single pass.

Why it matters: Skipping sorting leads to slower algorithms and harder-to-maintain code.

Quick: Do you think the merge step modifies the original intervals list? Commit to yes or no.

Common Belief: Merging always changes the original intervals list in place.

Reality: Usually, merging creates a new list to avoid side effects and keep input data intact.

Why it matters: Modifying input can cause bugs if the original data is needed later.

Expert Zone

1

Merging intervals assumes intervals are closed ranges; open or half-open intervals require adjusted overlap conditions.

2

The choice to merge touching intervals depends on the problem context; some applications treat touching intervals as separate.

3

In-place merging is possible but often avoided to keep code simpler and avoid bugs with input mutation.

When NOT to use

Do not use simple merge overlapping intervals when intervals change frequently or need fast queries; use interval trees or segment trees instead.

Production Patterns

In real systems, merging intervals is used in calendar apps to combine busy times, in database query optimizers to merge ranges, and in network systems to combine IP ranges for firewall rules.

Connections

Interval Trees

Builds-on

Understanding static merging helps grasp how interval trees manage dynamic intervals efficiently.

Sorting Algorithms

Depends-on

Knowing sorting is key to merging intervals highlights the importance of efficient sorting in many algorithms.

Resource Allocation in Operating Systems

Similar pattern

Merging overlapping intervals is like combining memory blocks or CPU time slices to optimize resource use.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

vector> mergeIntervals(vector>& intervals) {
vector> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}

Correct approach:

vector> mergeIntervals(vector>& intervals) {
sort(intervals.begin(), intervals.end());
vector> merged;
for (auto& interval : intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}

Root cause:

Skipping sorting causes intervals to be processed in wrong order, missing overlaps.

#2 Using '<' instead of '<=' when checking overlap, missing touching intervals.

Wrong approach:

if (merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}

Correct approach:

if (merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}

Root cause:

Misunderstanding whether touching intervals count as overlapping.

#3 Modifying the input intervals vector while iterating over it.

Wrong approach:

for (int i = 0; i < intervals.size(); ++i) {
if (i > 0 && intervals[i][0] <= intervals[i-1][1]) {
intervals[i-1][1] = max(intervals[i-1][1], intervals[i][1]);
intervals.erase(intervals.begin() + i);
--i;
}
}

Correct approach:

Use a separate vector to store merged intervals and do not erase from input during iteration.

Root cause:

Changing container size during iteration causes skipped elements or crashes.

Key Takeaways

Merging overlapping intervals means combining intervals that share any common points into one continuous interval.

Sorting intervals by their start time is essential to efficiently find and merge overlaps in a single pass.

Only adjacent intervals after sorting need to be checked for overlap, which reduces complexity from quadratic to linear.

Deciding whether touching intervals merge depends on the problem context and affects the merging condition.

For dynamic interval management or frequent updates, more advanced data structures like interval trees are needed.

Practice

1. What is the main purpose of the Merge Overlapping Intervals algorithm?

easy

A. To find the maximum interval length

B. To combine all intervals that overlap into a single continuous interval

C. To sort intervals in descending order

D. To remove all intervals that overlap

Solution

1. Step 1: Understand the problem goal

   The algorithm aims to merge intervals that share common parts so they become one continuous interval.

2. Step 2: Clarify what merging means

   Merging means combining overlapping intervals into one that covers the entire range of those intervals.

3. Final Answer:

   To combine all intervals that overlap into a single continuous interval -> Option B

4. Quick Check:

   Merge overlapping intervals = combine overlaps [OK]

Hint: Think of joining overlapping time slots into one [OK]

Common Mistakes:

• Confusing merging with sorting
• Thinking it removes intervals instead of combining
• Assuming it finds max length only

2. Which of the following C++ code snippets correctly sorts a vector of intervals by their start time before merging?

easy

A. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; });

B. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] > b[1]; });

C. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[1] < b[1]; });

D. std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] > b[0]; });

Solution

1. Step 1: Identify sorting by start time

   We need to sort intervals by their first element (start time) in ascending order.

2. Step 2: Check lambda comparator correctness

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); uses a lambda that compares a[0] < b[0], which sorts ascending by start time correctly.

3. Final Answer:

   std::sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a[0] < b[0]; }); -> Option A

4. Quick Check:

   Sort by start ascending = a[0] < b[0] [OK]

Hint: Sort intervals by start ascending using a lambda [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Sorting in descending order
• Using default sort without comparator on vector of vectors

3. What is the output of the following C++ code that merges overlapping intervals?

std::vector intervals = {{1,3},{2,6},{8,10},{15,18}};
// After merging overlapping intervals
// Print merged intervals
for (auto &interval : merged) {
    std::cout << "[" << interval[0] << "," << interval[1] << "] ";
}

medium

A. [1,6] [8,10] [15,18]

B. [1,3] [2,6] [8,10] [15,18]

C. [1,6] [2,6] [8,10] [15,18]

D. [1,3] [8,10] [15,18]

Solution

1. Step 1: Sort intervals by start time

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

2. Step 2: Merge overlapping intervals

   [1,3] and [2,6] overlap, merge to [1,6]. Others remain separate.

3. Final Answer:

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

4. Quick Check:

   Merged intervals = [1,6], [8,10], [15,18] [OK]

Hint: Merge intervals by expanding end if overlap found [OK]

Common Mistakes:

• Not merging overlapping intervals
• Printing original intervals without merge
• Merging incorrectly leaving duplicates

4. Identify the bug in this C++ code snippet for merging intervals:

std::vector mergeIntervals(std::vector &intervals) {
    std::vector merged;
    for (auto &interval : intervals) {
        if (merged.empty() || merged.back()[1] < interval[0]) {
            merged.push_back(interval);
        } else {
            merged.back()[1] = std::max(merged.back()[1], interval[1]);
        }
    }
    return merged;
}

medium

A. Pushing intervals without checking overlap

B. Using std::max incorrectly

C. Intervals are not sorted before merging

D. Returning merged by reference instead of value

Solution

1. Step 1: Check preconditions for merging

   Merging requires intervals sorted by start time to work correctly.

2. Step 2: Identify missing sorting step

   The code does not sort intervals before merging, so overlapping intervals may be missed.

3. Final Answer:

   Intervals are not sorted before merging -> Option C

4. Quick Check:

   Sort intervals first to merge correctly [OK]

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

Common Mistakes:

• Skipping sorting step
• Assuming input is sorted
• Misusing std::max function

5. Given intervals [[1,4],[4,5],[7,9],[8,10]], what is the merged output after applying the merge overlapping intervals algorithm?

hard

A. [[1,10]]

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

C. [[1,4],[5,7],[8,10]]

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

Solution

1. Step 1: Sort intervals by start time

   Intervals are already sorted: [1,4], [4,5], [7,9], [8,10]

2. Step 2: Merge overlapping or touching intervals

   [1,4] and [4,5] touch at 4, merge to [1,5]. [7,9] and [8,10] overlap, merge to [7,10].

3. Final Answer:

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

4. Quick Check:

   Touching intervals merge too [OK]

Hint: Merge intervals that overlap or touch at boundaries [OK]

Common Mistakes:

• Not merging intervals that touch at endpoints
• Leaving intervals separate when they overlap
• Merging all intervals incorrectly into one