Merge Overlapping Intervals in DSA C++ - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Initialize merged list empty

↓

For each interval

↓

Check overlap with last merged

↓

Merge intervals

↓

Repeat

↓

Return merged

Sort intervals first, then go through each interval to merge if overlapping or add if not.

Execution Sample

DSA C++

intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sort intervals
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
  if not merged or merged[-1][1] < interval[0]:
    merged.append(interval)
  else:
    merged[-1][1] = max(merged[-1][1], interval[1])
return merged

This code merges overlapping intervals from a list.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged Intervals State
1	Sort intervals	[1,3]	N/A	Sorted intervals: [[1,3],[2,6],[8,10],[15,18]]	[[1,3]]
2	Process interval	[2,6]	[1,3]	Overlap detected, merge to [1,6]	[[1,6]]
3	Process interval	[8,10]	[1,6]	No overlap, add [8,10]	[[1,6],[8,10]]
4	Process interval	[15,18]	[8,10]	No overlap, add [15,18]	[[1,6],[8,10],[15,18]]
5	End	N/A	N/A	All intervals processed	[[1,6],[8,10],[15,18]]

💡 All intervals processed and merged where overlapping.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]

Key Moments - 3 Insights

Why do we sort intervals before merging?

Sorting ensures intervals are in order by start time, so overlapping intervals come one after another, making merging straightforward as shown in step 1 of the execution_table.

How do we know if two intervals overlap?

We check if the current interval's start is less than or equal to the last merged interval's end. If yes, they overlap and we merge by updating the end, as seen in step 2.

What happens if intervals do not overlap?

If no overlap, we simply add the current interval to the merged list without merging, as shown in steps 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the merged interval after merging?

A [1,3]

B [2,6]

C [1,6]

D [3,6]

💡 Hint

Check the 'Merged Intervals State' column at step 2 in execution_table.

At which step does the algorithm add a new interval without merging?

A Step 2

B Step 3

C Step 1

D Step 5

💡 Hint

Look for 'No overlap, add' in the 'Action' column in execution_table.

If the intervals were not sorted first, what would likely happen?

A Some overlapping intervals might not merge properly

B Merging would still work correctly

C The merged list would be empty

D The algorithm would run faster

💡 Hint

Refer to the key_moments about why sorting is important before merging.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize empty merged list.
3. For each interval, if it overlaps with last merged, merge them.
4. Else, add interval to merged list.
5. Return merged list of intervals.

Full Transcript

To merge overlapping intervals, first sort the intervals by their start times. Then, create an empty list to hold merged intervals. Go through each interval in order. If the current interval overlaps with the last interval in the merged list, merge them by updating the end time. If not overlapping, add the current interval to the merged list. Continue until all intervals are processed. The final merged list contains intervals without overlaps.

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