Merge Overlapping Intervals in DSA C++ - 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 that no intervals in the result overlap.

beginner

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

Sorting by start time helps us easily find overlapping intervals by comparing each interval with the previous merged interval in order.

beginner

In the Merge Overlapping Intervals algorithm, what do you do when the current interval does NOT overlap with the last merged interval?

You add the current interval as a new separate interval to the merged list because it does not overlap with any previous intervals.

intermediate

How do you merge two overlapping intervals [a, b] and [c, d] where c ≤ b?

You create a new interval [a, max(b, d)] that covers both intervals without gaps.

intermediate

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

O(n log n) because sorting the intervals takes O(n log n) time, and merging them in one pass takes O(n) time.

What is the first step in merging overlapping intervals?

A Reverse the intervals

B Sort intervals by end time

C Remove duplicates

D Sort intervals by start time

Sorting intervals by their start time helps to easily identify overlaps in order.

If interval [1, 5] and [4, 8] overlap, what is the merged interval?

A [1, 4]

B [4, 8]

C [1, 8]

D [5, 8]

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

What do you do if the current interval starts after the last merged interval ends?

A Add current interval as new

B Merge them

C Ignore current interval

D Remove last merged interval

If intervals do not overlap, add the current interval separately.

Which data structure is commonly used to store merged intervals during the process?

A Stack

B List or vector

C Hash map

D Queue

A list or vector is used to store merged intervals in order.

What is the overall time complexity of the merge overlapping intervals algorithm?

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

Sorting takes O(n log n), merging takes O(n), so total is O(n log n).

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

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

Describe why sorting intervals is important before merging and what could go wrong if you skip sorting.

Consider how unordered intervals affect overlap detection.

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