Merge Overlapping Intervals in DSA C++

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 slots booked on a calendar. If some bookings overlap, you merge them into one longer booking to avoid confusion.

Intervals: [1,3] -> [2,6] -> [8,10] -> [15,18]
Timeline: 1---3  2----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 to easily find overlapping intervals by comparing neighbors

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

merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Compare next interval [2,6] with last merged [1,3], they overlap

merged: [1,6]

Why: Since 2 ≤ 3, intervals overlap, so merge by extending end to max(3,6)=6

Step 4: Compare next interval [8,10] with last merged [1,6], no overlap

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

Why: 8 > 6 means no overlap, so add new interval

Step 5: Compare next interval [15,18] with last merged [8,10], no overlap

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

Why: 15 > 10 means no overlap, add new interval

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Interval {
public:
    int start, end;
    Interval(int s, int e) : start(s), end(e) {}
};

vector<Interval> mergeIntervals(vector<Interval>& intervals) {
    if (intervals.empty()) return {};
    // Sort intervals by start time
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });

    vector<Interval> merged;
    merged.push_back(intervals[0]); // start with first interval

    for (int i = 1; i < intervals.size(); i++) {
        // If current interval overlaps with last merged
        if (intervals[i].start <= merged.back().end) {
            // Merge by extending the end if needed
            merged.back().end = max(merged.back().end, intervals[i].end);
        } else {
            // No overlap, add current interval
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

int main() {
    vector<Interval> intervals = {Interval(1,3), Interval(2,6), Interval(8,10), Interval(15,18)};
    vector<Interval> merged = mergeIntervals(intervals);
    for (auto& interval : merged) {
        cout << "[" << interval.start << "," << interval.end << "] ";
    }
    cout << endl;
    return 0;
}

sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; });

Sort intervals by their start time to process in order

merged.push_back(intervals[0]);

Initialize merged list with first interval

if (intervals[i].start <= merged.back().end) {

Check if current interval overlaps with last merged interval

merged.back().end = max(merged.back().end, intervals[i].end);

Extend the end of last merged interval to cover current interval

merged.push_back(intervals[i]);

Add current interval as new merged interval if no overlap

Output

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

Complexity Analysis

Time: O(n log n) because sorting the 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 compares every interval with every other leading to O(n^2), this method is efficient by sorting first

Edge Cases

empty intervals list

returns empty merged list without error

DSA C++

if (intervals.empty()) return {};

all intervals non-overlapping

merged list is same as input intervals

DSA C++

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

all intervals overlapping into one big interval

merged list contains single interval covering all

DSA C++

merged.back().end = max(merged.back().end, intervals[i].end);

When to Use This Pattern

When you see a problem asking to combine overlapping ranges or time slots, reach for the merge intervals pattern because sorting and merging neighbors simplifies the problem.

Common Mistakes

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

Mistake: Extending merged interval incorrectly by not taking max end
Fix: Use max of current merged end and new interval end to cover full overlap

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you need to simplify overlapping ranges into distinct non-overlapping intervals.

Sort intervals by start time, then merge neighbors by extending ends if they overlap.

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