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 separate.

Execution Sample

DSA C#

int[][] intervals = { new int[]{1,3}, new int[]{2,6}, new int[]{8,10}, new int[]{15,18} };
var merged = Merge(intervals);
// Merge merges overlapping intervals into combined intervals

This code merges overlapping intervals from the input list.

Execution Table

Step	Operation	Current Interval	Last Merged Interval	Action	Merged List State
1	Sort intervals	N/A	N/A	Intervals sorted by start	[]
2	Initialize merged list	N/A	N/A	Start with empty merged list	[]
3	Process interval	[1,3]	N/A	Add first interval to merged	[[1,3]]
4	Process interval	[2,6]	[1,3]	Overlap detected, merge to [1,6]	[[1,6]]
5	Process interval	[8,10]	[1,6]	No overlap, add interval	[[1,6], [8,10]]
6	Process interval	[15,18]	[8,10]	No overlap, add interval	[[1,6], [8,10], [15,18]]
7	Return result	N/A	N/A	Return merged intervals	[[1,6], [8,10], [15,18]]

💡 All intervals processed, merged list returned

Variable Tracker

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

Key Moments - 3 Insights

Why do we merge intervals when current start is less than or equal to last merged end?

Because intervals overlap or touch, so we combine them into one bigger interval as shown in step 4 where [2,6] overlaps with [1,3].

Why do we add the current interval directly when there is no overlap?

Because intervals are sorted, no overlap means current interval starts after last merged ends, so it is separate and added as new interval (steps 5 and 6).

Why do we sort intervals first before merging?

Sorting ensures intervals are in order by start time, so we can merge in one pass without missing overlaps (step 1).

Visual Quiz - 3 Questions

Look at the execution table, what is the merged list state after processing the second interval?

A [[1,6]]

B [[1,3]]

C [[2,6]]

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

💡 Hint

Check step 4 in the execution table where merging happens.

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

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Action' column in the execution table for when intervals are added without merging.

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

A Merging would still work correctly

B Some overlapping intervals might not merge properly

C The merged list would be empty

D The code would crash

💡 Hint

Refer to the importance of sorting in the concept flow and step 1.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize empty merged list.
3. For each interval, compare with last merged:
   - If overlapping, merge by updating end.
   - Else, add as new interval.
4. Return merged list of combined 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 one by one. 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 as is. Continue until all intervals are processed. Finally, return the merged list which contains combined intervals without overlaps.

Practice

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

easy

A. To find the maximum number of intervals

B. To sort intervals by their length

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

D. To split intervals into smaller parts

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: Identify the correct purpose

   Among the options, only combining overlapping intervals matches the goal.

3. Final Answer:

   To combine all intervals that overlap into a single 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
• Thinking it splits intervals instead of combining
• Assuming it counts intervals

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

easy

A. intervals.OrderBy(x => x.Length);

B. intervals.OrderByDescending(x => x.End);

C. intervals.Sort((a, b) => b.Start.CompareTo(a.Start));

D. intervals.Sort((a, b) => a.Start.CompareTo(b.Start));

Solution

1. Step 1: Identify sorting by start time

   We need to sort intervals by their start property in ascending order.

2. Step 2: Check each option

   intervals.Sort((a, b) => a.Start.CompareTo(b.Start)); uses Sort with CompareTo on Start ascending, which is correct. Others sort by end descending, start descending, or length, which are incorrect for merging.

3. Final Answer:

   intervals.Sort((a, b) => a.Start.CompareTo(b.Start)); -> Option D

4. Quick Check:

   Sort by start ascending = intervals.Sort((a, b) => a.Start.CompareTo(b.Start)); [OK]

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

Common Mistakes:

• Sorting by end time instead of start
• Sorting descending instead of ascending
• Sorting by interval length

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

var intervals = new List<(int Start, int End)>{ (1,3), (2,6), (8,10), (15,18) };
intervals.Sort((a,b) => a.Start.CompareTo(b.Start));
var merged = new List<(int, int)>();
foreach(var interval in intervals) {
  if(merged.Count == 0 || merged[^1].End < interval.Start) {
    merged.Add(interval);
  } else {
    var last = merged[^1];
    merged[^1] = (last.Start, Math.Max(last.End, interval.End));
  }
}
foreach(var i in merged) Console.Write($"({i.Start},{i.End}) ");

medium

A. (1,6) (8,10) (15,18)

B. (1,3) (2,6) (8,10) (15,18)

C. (1,10) (15,18)

D. (1,6) (2,10) (15,18)

Solution

1. Step 1: Sort intervals by start

   Sorted intervals: (1,3), (2,6), (8,10), (15,18)

2. Step 2: Merge overlapping intervals

   (1,3) and (2,6) overlap, merged to (1,6). Others do not overlap, so final merged list is (1,6), (8,10), (15,18).

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 comparing current start with last merged end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Merging intervals incorrectly by extending start
• Printing original intervals without merging

4. The following code attempts to merge overlapping intervals but has a bug. What is the bug?

var intervals = new List<(int Start, int End)>{ (1,4), (4,5) };
intervals.Sort((a,b) => a.Start.CompareTo(b.Start));
var merged = new List<(int, int)>();
foreach(var interval in intervals) {
  if(merged.Count == 0 || merged[^1].End <= interval.Start) {
    merged.Add(interval);
  } else {
    var last = merged[^1];
    merged[^1] = (last.Start, Math.Max(last.End, interval.End));
  }
}
foreach(var i in merged) Console.Write($"({i.Start},{i.End}) ");

medium

A. The condition should use < instead of <= to merge touching intervals

B. The intervals are not sorted before merging

C. The merged list is not initialized

D. The code does not handle empty input

Solution

1. Step 1: Analyze the merge condition

   The condition uses merged[^1].End <= interval.Start, which treats touching intervals as non-overlapping.

2. Step 2: Identify correct condition for merging

   To merge intervals that touch (like (1,4) and (4,5)), use < instead of <= so they merge into (1,5).

3. Final Answer:

   The condition should use < instead of <= to merge touching intervals -> Option A

4. Quick Check:

   Use < to merge touching intervals [OK]

Hint: Use strict less than to merge intervals that touch [OK]

Common Mistakes:

• Using <= causes touching intervals to not merge
• Forgetting to sort intervals
• Ignoring empty input cases

5. Given a list of intervals [(1,5), (2,3), (4,8), (10,12), (9,10)], what is the merged list after applying the merge overlapping intervals algorithm?

hard

A. [(1,5), (2,3), (4,8), (9,10), (10,12)]

B. [(1,8), (9,12)]

C. [(1,3), (4,8), (9,12)]

D. [(1,8), (10,12)]

Solution

1. Step 1: Sort intervals by start

   Sorted intervals: (1,5), (2,3), (4,8), (9,10), (10,12)

2. Step 2: Merge overlapping intervals step-by-step

   Merge (1,5) and (2,3) -> (1,5); merge (1,5) and (4,8) -> (1,8); merge (9,10) and (10,12) -> (9,12). Final merged intervals: (1,8), (9,12).

3. Final Answer:

   [(1,8), (9,12)] -> Option B

4. Quick Check:

   Merged intervals = [(1,8), (9,12)] [OK]

Hint: Sort then merge overlapping or touching intervals stepwise [OK]

Common Mistakes:

• Not merging intervals that overlap inside others
• Missing to merge touching intervals
• Returning original intervals without merging