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

↓

Done

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

Execution Sample

DSA C

int intervals[][2] = {{1,3},{2,6},{8,10},{15,18}};
// Sort by start
// Merge overlapping intervals
// Result: {{1,6},{8,10},{15,18}}

This code merges overlapping intervals from a list of intervals.

Execution Table

Step	Operation	Current Interval	Merged List Before	Action	Merged List After	Visual State
1	Sort intervals	[1,3],[2,6],[8,10],[15,18]	[]	Sort by start	[1,3],[2,6],[8,10],[15,18]	[1,3] -> [2,6] -> [8,10] -> [15,18] -> null
2	Initialize merged list	[1,3]	[]	Add first interval	[1,3]	[1,3] -> null
3	Check overlap	[2,6]	[1,3]	2 <= 3 overlap	Merge to [1,6]	[1,6] -> null
4	Check overlap	[8,10]	[1,6]	8 > 6 no overlap	Add [8,10]	[1,6] -> [8,10] -> null
5	Check overlap	[15,18]	[1,6],[8,10]	15 > 10 no overlap	Add [15,18]	[1,6] -> [8,10] -> [15,18] -> null
6	End	N/A	[1,6],[8,10],[15,18]	All intervals processed	[1,6],[8,10],[15,18]	[1,6] -> [8,10] -> [15,18] -> null

💡 All intervals processed and merged where overlapping.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	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]]
current_interval	N/A	[1,3]	[2,6]	[8,10]	[15,18]	N/A

Key Moments - 3 Insights

Why do we merge intervals when current start <= last merged end?

Because intervals overlap if the current interval starts before or exactly when the last merged interval ends. See step 3 in execution_table where [2,6] overlaps with [1,3].

Why do we add the current interval to merged list when no overlap?

Because intervals do not overlap if current start is greater than last merged end, so we keep them separate. See step 4 and 5 where [8,10] and [15,18] are added separately.

Why do we sort intervals first?

Sorting ensures intervals are in order by start time, so merging can be done in one pass. Without sorting, overlapping intervals might be missed.

Visual Quiz - 3 Questions

Look at the execution_table, what is the merged list after step 3?

A [[1,3]]

B [[1,6]]

C [[2,6]]

D [[1,3],[2,6]]

💡 Hint

Check the 'Merged List After' column in step 3 of execution_table.

At which step does the condition for no overlap first occur?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Action' column in execution_table where it says 'no overlap'.

If intervals were not sorted, what would change in the execution_table?

A Merging might miss overlapping intervals

B Intervals would be merged correctly anyway

C Merged list would be empty

D Sorting step would be skipped but no effect

💡 Hint

Refer to the key_moments explanation about sorting importance.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize merged list with first interval.
3. For each next interval, if it overlaps with last merged, merge them.
4. Else, add interval to merged list.
5. Result is merged intervals without overlap.

Full Transcript

To merge overlapping intervals, first sort the intervals by their start times. Then start with an empty merged list and add the first interval. For each next interval, check if it overlaps with the last interval in the merged list. Overlap means the current interval's start is less than or equal to the last merged interval's end. If overlapping, merge by updating the end of the last merged interval to the maximum end of both. If no overlap, add the current interval as a new entry in the merged list. Continue until all intervals are processed. The final merged list contains intervals without overlaps.

Practice

1. What is the main goal of the Merge Overlapping Intervals problem?

easy

A. Find the maximum number of intervals without overlap

B. Sort intervals by their end times only

C. Combine all intervals that overlap into one continuous interval

D. Count how many intervals are in the list

Solution

1. Step 1: Understand the problem goal

   The problem asks to merge intervals that overlap, so they become one continuous interval without gaps.

2. Step 2: Identify the correct description

   Combine all intervals that overlap into one continuous interval correctly describes merging overlapping intervals into one combined interval.

3. Final Answer:

   Combine all intervals that overlap into one continuous interval -> Option C

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 only
• Counting intervals instead of merging
• Ignoring overlaps

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

easy

A. qsort(intervals, n, sizeof(Interval), compareStart);

B. qsort(intervals, n, sizeof(Interval), compareLength);

C. sort(intervals.begin(), intervals.end());

D. qsort(intervals, n, sizeof(Interval), compareEnd);

Solution

1. Step 1: Identify sorting criteria for merging

   Intervals must be sorted by their start time to merge correctly.

2. Step 2: Match sorting function

   qsort(intervals, n, sizeof(Interval), compareStart); uses compareStart which sorts by start time, correct for merging.

3. Final Answer:

   qsort(intervals, n, sizeof(Interval), compareStart); -> Option A

4. Quick Check:

   Sort by start time = qsort with compareStart [OK]

Hint: Sort intervals by start time before merging [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using C++ sort syntax in C code
• Sorting by interval length

3. What is the output of the merged intervals after running this code on input intervals: [[1,3], [2,6], [8,10], [15,18]]?

Intervals = [[1,3], [2,6], [8,10], [15,18]]
// After sorting by start time
// Merge overlapping intervals
// Print merged intervals

medium

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

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

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

D. [[1,6], [8,15], [18,18]]

Solution

1. Step 1: Sort intervals by start time

   Intervals are already sorted: [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 do not overlap.

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 if current start ≤ previous end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Merging non-overlapping intervals
• Incorrectly merging intervals with gaps

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

Interval merged[100];
int m = 0;
merged[0] = intervals[0];
for (int i = 1; i < n; i++) {
  if (intervals[i].start <= merged[m].end) {
    merged[m].end = intervals[i].end;
  } else {
    m++;
    merged[m] = intervals[i];
  }
}

medium

A. Loop starts from 0 instead of 1

B. It incorrectly updates the end of the previous interval without checking max end

C. Uses <= instead of < in the overlap condition

D. It compares start with start instead of end

Solution

1. Step 1: Analyze interval merging logic

   When intervals overlap, end should be max of both ends, not just assigned.

2. Step 2: Identify incorrect update

   Code sets previous end to current end without max check, causing wrong merges.

3. Final Answer:

   It incorrectly updates the end of the previous interval without checking max end -> Option B

4. Quick Check:

   Use max end when merging intervals [OK]

Hint: Always update end to max of overlapping intervals [OK]

Common Mistakes:

• Assigning end without max check
• Using strict < instead of <= for touching intervals
• Wrong loop start index

5. Given intervals [[1,4], [4,5], [5,6], [7,8]], what is the merged output if intervals that touch at boundaries are considered overlapping?

hard

A. [[1,8]]

B. [[1,4], [4,5], [5,6], [7,8]]

C. [[1,5], [5,6], [7,8]]

D. [[1,6], [7,8]]

Solution

1. Step 1: Understand touching intervals as overlapping

   Intervals that share boundary points merge: [1,4] and [4,5] merge to [1,5], then with [5,6] to [1,6].

2. Step 2: Merge intervals accordingly

   After merging first three intervals, [7,8] remains separate.

3. Final Answer:

   [[1,6], [7,8]] -> Option D

4. Quick Check:

   Touching intervals merge into one [OK]

Hint: Treat intervals with end == start as overlapping [OK]

Common Mistakes:

• Not merging touching intervals
• Merging all intervals incorrectly
• Ignoring boundary overlap condition