Merge Overlapping Intervals in DSA C# - Deep Dive

Overview - Merge Overlapping Intervals

What is it?

Merge Overlapping Intervals is a way to combine intervals that share some common part into one bigger interval. Imagine you have many time slots or ranges, and some of them overlap or touch each other. This method helps you join those overlapping parts so you get fewer, bigger intervals without any overlaps.

Why it matters

Without merging overlapping intervals, you might count the same time or range multiple times, causing confusion or errors. For example, if you schedule meetings that overlap, you might think you have more free time than you actually do. Merging intervals helps in planning, booking, and analyzing ranges correctly and efficiently.

Where it fits

Before learning this, you should understand arrays or lists and sorting basics. After mastering merging intervals, you can explore interval trees, scheduling algorithms, and advanced range queries.

Mental Model

Core Idea

Combine intervals that touch or overlap into one continuous interval to simplify and avoid counting the same parts multiple times.

Think of it like...

Think of intervals like pieces of a ribbon laid on a table. If some pieces overlap or touch, you tape them together to make one longer ribbon instead of many small pieces.

Intervals before merging:
[1, 3], [2, 6], [8, 10], [15, 18]

Sorted and merged intervals:
[1, 6], [8, 10], [15, 18]

Visual:
┌─────┐
│1  3 │
  ┌───────┐
  │ 2    6│

Merged:
┌─────────────┐
│1          6 │

Separate:
      ┌─────┐
      │8 10 │

           ┌───────┐
           │15   18│

Build-Up - 7 Steps

1

Foundation

Understanding Intervals and Overlaps

Concept: Intervals are ranges defined by a start and end point; overlapping means two intervals share some common points.

An interval is like a segment on a number line, for example [1, 3] means from 1 to 3. Two intervals overlap if they share any points. For example, [1, 3] and [2, 4] overlap because 2 and 3 are in both.

Result

You can identify if two intervals overlap by checking if the start of one is less than or equal to the end of the other and vice versa.

Understanding what overlap means is the foundation for merging intervals because only overlapping or touching intervals should be combined.

2

Foundation

Sorting Intervals by Start Time

Concept: Sorting intervals by their start point helps process them in order and makes merging easier.

Given intervals like [8, 10], [1, 3], [2, 6], sort them by their start values to get [1, 3], [2, 6], [8, 10]. This order lets you compare each interval with the previous one to check for overlaps.

Result

Sorted intervals: [1, 3], [2, 6], [8, 10]

Sorting is crucial because it guarantees that when you move through intervals, you only need to compare with the last merged interval, simplifying the logic.

3

Intermediate

Merging Two Overlapping Intervals

🤔Before reading on: If you have intervals [1, 4] and [3, 5], do you think the merged interval is [1, 5] or [3, 4]? Commit to your answer.

Concept: When two intervals overlap, merge them by taking the smallest start and the largest end.

For intervals [1, 4] and [3, 5], since they overlap (3 ≤ 4), merge them into [1, 5]. The merged interval covers all points from the earliest start to the latest end.

Result

Merged interval: [1, 5]

Knowing how to merge two intervals correctly is the key step that repeats when merging many intervals.

4

Intermediate

Iterative Merging of Multiple Intervals

🤔Before reading on: When merging [1, 3], [2, 6], [8, 10], do you think the final merged list has 2 or 3 intervals? Commit to your answer.

Concept: Process intervals one by one after sorting, merging with the last merged interval if they overlap, or adding a new interval if they don't.

Start with the first interval [1, 3]. Compare it with [2, 6]: they overlap, so merge to [1, 6]. Next, compare [1, 6] with [8, 10]: no overlap, so add [8, 10] as a new interval.

Result

Merged intervals: [1, 6], [8, 10]

Iterative merging reduces complexity by always comparing with the last merged interval, avoiding repeated checks.

5

Intermediate

Handling Edge Cases in Merging

🤔Before reading on: If intervals are [1, 4], [4, 5], do you think they merge into one or stay separate? Commit to your answer.

Concept: Intervals that touch at the boundary (end of one equals start of another) are considered overlapping and should be merged.

For [1, 4] and [4, 5], since 4 equals 4, merge into [1, 5]. This prevents gaps where intervals just touch but don't overlap numerically.

Result

Merged interval: [1, 5]

Recognizing touching intervals as overlapping ensures no gaps remain in the merged result, which is important in scheduling and range coverage.

6

Advanced

Efficient C# Implementation with Lists

🤔Before reading on: Do you think using a List and sorting it is enough for efficient merging, or do you need a special data structure? Commit to your answer.

Concept: Use a List of intervals, sort by start, then iterate and merge using a stack or result list for efficiency.

Code example: using System; using System.Collections.Generic; public class Interval { public int Start, End; public Interval(int s, int e) { Start = s; End = e; } } public class Solution { public static List Merge(List intervals) { intervals.Sort((a, b) => a.Start.CompareTo(b.Start)); List merged = new List(); foreach (var interval in intervals) { if (merged.Count == 0 || merged[^1].End < interval.Start) { merged.Add(new Interval(interval.Start, interval.End)); } else { merged[^1].End = Math.Max(merged[^1].End, interval.End); } } return merged; } } This code sorts intervals, then merges by comparing with the last merged interval.

Result

Merged intervals returned as a List with no overlaps.

Using built-in sorting and a simple list for merging is both clear and efficient, suitable for most practical uses.

7

Expert

Surprising Behavior with Large or Nested Intervals

🤔Before reading on: If you have intervals [1, 10], [2, 3], [4, 8], do you think the smaller intervals affect the merged result? Commit to your answer.

Concept: Smaller intervals fully inside a larger one do not change the merged interval but must be considered during merging to avoid duplicates.

Given [1, 10], [2, 3], [4, 8], after sorting, the first interval covers all others. The merge process keeps [1, 10] only, ignoring nested intervals as they add no new range. This shows that merging handles containment naturally without extra checks.

Result

Final merged interval: [1, 10]

Understanding that nested intervals don't expand the merged range prevents unnecessary complexity and helps optimize interval processing.

Under the Hood

Internally, merging intervals relies on sorting to order intervals by start time. Then, it iterates through the sorted list, comparing each interval with the last merged one. If they overlap or touch, it updates the end of the last merged interval to the maximum end of both. Otherwise, it adds the new interval as separate. This process ensures a single pass after sorting, making it efficient.

Why designed this way?

This approach was chosen because sorting simplifies the problem by arranging intervals in a predictable order. Without sorting, checking overlaps would require comparing every interval with every other, leading to slower performance. The design balances simplicity and efficiency, avoiding complex data structures for most use cases.

Sorted intervals:
┌─────────────┐
│Interval 1   │
│Start: s1    │
│End:   e1    │
└─────────────┘
       ↓
Compare with next interval:
┌─────────────┐   ┌─────────────┐
│Interval 2   │ -> │Check overlap│
│Start: s2    │   │s2 <= e1?    │
│End:   e2    │   └─────────────┘
└─────────────┘
       ↓
If overlap:
Update e1 = max(e1, e2)
Else:
Add Interval 2 to merged list
Repeat for all intervals

Myth Busters - 3 Common Misconceptions

Quick: Do you think intervals that only touch at the boundary should be merged? Commit to yes or no.

Common Belief: Intervals must overlap by at least one point to be merged; touching at the boundary is not enough.

Reality: Intervals that touch at the boundary (end of one equals start of another) are considered overlapping and should be merged.

Why it matters: Failing to merge touching intervals causes gaps in coverage, leading to incorrect results in scheduling or range calculations.

Quick: Do you think sorting intervals by end time works as well as sorting by start time for merging? Commit to yes or no.

Common Belief: Sorting intervals by their end time is enough to merge them correctly.

Reality: Sorting by start time is necessary because merging depends on processing intervals in ascending order of their start points.

Why it matters: Sorting by end time can cause missed overlaps and incorrect merges, leading to wrong final intervals.

Quick: Do you think nested intervals need special handling during merging? Commit to yes or no.

Common Belief: Nested intervals require extra checks and special logic to merge correctly.

Reality: Nested intervals are naturally handled by the standard merging process without extra code.

Why it matters: Overcomplicating nested intervals wastes time and can introduce bugs.

Expert Zone

1

Merging intervals is stable only if the sorting algorithm preserves order for intervals with the same start; this can affect output order but not correctness.

2

In some cases, intervals may have open or closed ends (e.g., (1,3) vs [1,3]); merging logic must adjust accordingly for precise applications.

3

When intervals represent resources with weights or priorities, merging must consider these attributes, complicating the simple merge logic.

When NOT to use

Do not use simple merge when intervals have additional attributes like weights or when intervals are dynamic and frequently updated; instead, use interval trees or segment trees for efficient queries and updates.

Production Patterns

In real systems, merging intervals is used in calendar apps to combine busy times, in database query optimizers to merge range scans, and in network systems to combine IP ranges for firewall rules.

Connections

Interval Trees

Builds-on

Understanding merging intervals helps grasp interval trees, which efficiently manage many intervals with fast overlap queries.

Calendar Scheduling

Application

Merging intervals directly applies to scheduling meetings by combining busy times to find free slots.

Genetics - DNA Sequence Alignment

Similar pattern

Merging overlapping intervals is conceptually similar to aligning overlapping DNA sequences to form a continuous genome segment.

Common Pitfalls

#1 Not sorting intervals before merging.

Wrong approach:

List intervals = new List { new Interval(8, 10), new Interval(1, 3), new Interval(2, 6) };
// Directly merging without sorting
List merged = new List();
foreach (var interval in intervals) {
if (merged.Count == 0 || merged[^1].End < interval.Start) {
merged.Add(interval);
} else {
merged[^1].End = Math.Max(merged[^1].End, interval.End);
}
}

Correct approach:

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

Root cause:

Skipping sorting causes intervals to be processed out of order, leading to missed overlaps and incorrect merges.

#2 Treating touching intervals as separate.

Wrong approach:

if (merged[^1].End <= interval.Start) {
merged.Add(interval);
} else {
merged[^1].End = Math.Max(merged[^1].End, interval.End);
}

Correct approach:

if (merged[^1].End < interval.Start) {
merged.Add(interval);
} else {
merged[^1].End = Math.Max(merged[^1].End, interval.End);
}

Root cause:

Using <= instead of < excludes intervals that touch at boundaries from merging.

#3 Modifying input intervals directly without copying.

Wrong approach:

foreach (var interval in intervals) {
if (merged.Count == 0 || merged[^1].End < interval.Start) {
merged.Add(interval);
} else {
merged[^1].End = Math.Max(merged[^1].End, interval.End);
}
}
// This changes original intervals

Correct approach:

foreach (var interval in intervals) {
if (merged.Count == 0 || merged[^1].End < interval.Start) {
merged.Add(new Interval(interval.Start, interval.End));
} else {
merged[^1].End = Math.Max(merged[^1].End, interval.End);
}
}
// Keeps original intervals unchanged

Root cause:

Directly modifying input intervals can cause side effects if original data is needed later.

Key Takeaways

Merging overlapping intervals simplifies multiple ranges into fewer, continuous intervals without overlaps.

Sorting intervals by their start time is essential before merging to ensure correct and efficient processing.

Intervals that touch at boundaries should be merged to avoid gaps in coverage.

The merging process naturally handles nested intervals without extra complexity.

Efficient merging uses a single pass after sorting, making it practical for many real-world applications.

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