Merge Overlapping Intervals in DSA C#

Mental Model

We combine intervals that touch or overlap into one bigger interval so no two intervals cover the same range twice.

Analogy: Imagine you have several time slots booked on a calendar. If two bookings overlap or touch, you merge them into one longer booking to avoid confusion.

Intervals before merge:
[1,3] -> [2,6] -> [8,10] -> [15,18]

Intervals after merge:
[1,6] -> [8,10] -> [15,18]

Dry Run Walkthrough

Input: intervals: [1,3], [2,6], [8,10], [15,18]

Goal: Merge all overlapping intervals into combined intervals without overlaps

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18]

Why: Sorting helps us check intervals in order to merge overlaps easily

Step 2: Start with first interval [1,3] in merged list

merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Compare next interval [2,6] with last merged [1,3], they overlap

merged: [1,6]

Why: Since 2 ≤ 3, intervals overlap, so merge by extending end to max(3,6)=6

Step 4: Compare next interval [8,10] with last merged [1,6], no overlap

merged: [1,6] -> [8,10]

Why: 8 > 6 means no overlap, so add new interval

Step 5: Compare next interval [15,18] with last merged [8,10], no overlap

merged: [1,6] -> [8,10] -> [15,18]

Why: 15 > 10 means no overlap, so add new interval

Result:

merged intervals: [1,6] -> [8,10] -> [15,18]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class Interval {
    public int start;
    public int end;
    public Interval(int s, int e) { start = s; end = e; }
    public override string ToString() => $"[{start},{end}]";
}

public class Solution {
    public static List<Interval> MergeIntervals(List<Interval> intervals) {
        if (intervals.Count == 0) return new List<Interval>();

        intervals.Sort((a, b) => a.start.CompareTo(b.start));
        // sort intervals by start time

        List<Interval> merged = new List<Interval>();
        merged.Add(intervals[0]);
        // start merged list with first interval

        for (int i = 1; i < intervals.Count; i++) {
            var current = intervals[i];
            var last = merged[merged.Count - 1];
            if (current.start <= last.end) {
                last.end = Math.Max(last.end, current.end);
                // merge overlapping intervals by extending end
            } else {
                merged.Add(current);
                // no overlap, add current interval
            }
        }
        return merged;
    }

    public static void Main() {
        var intervals = new List<Interval> {
            new Interval(1,3), new Interval(2,6), new Interval(8,10), new Interval(15,18)
        };
        var merged = MergeIntervals(intervals);
        foreach (var interval in merged) {
            Console.Write(interval + " ");
        }
    }
}

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

sort intervals by start time to process in order

merged.Add(intervals[0]);

initialize merged list with first interval as base

for (int i = 1; i < intervals.Count; i++) {

iterate over intervals starting from second to check for overlaps

var current = intervals[i];

current interval to compare

var last = merged[merged.Count - 1];

get last merged interval to compare with current

if (current.start <= last.end) {

check if current interval overlaps with last merged

last.end = Math.Max(last.end, current.end);

merge by extending the end of last merged interval

else { merged.Add(current); }

no overlap, add current interval as new merged interval

Output

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

Complexity Analysis

Time: O(n log n) because sorting the intervals takes O(n log n) and merging takes O(n)

Space: O(n) because in worst case no intervals overlap and merged list stores all intervals

vs Alternative: Naive approach compares every pair which is O(n^2), sorting plus one pass is more efficient

Edge Cases

empty list

returns empty list immediately

DSA C#

if (intervals.Count == 0) return new List<Interval>();

all intervals non-overlapping

merged list is same as input list

DSA C#

else { merged.Add(current); }

all intervals overlapping

merged list contains one interval covering all

DSA C#

last.end = Math.Max(last.end, current.end);

When to Use This Pattern

When you see a problem asking to combine or simplify overlapping ranges, reach for the Merge Overlapping Intervals pattern because sorting and merging in one pass solves it efficiently.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Sort intervals by start time first to ensure correct merging order

Mistake: Adding current interval to merged list even when overlapping
Fix: Update the end of last merged interval instead of adding a new one when overlapping

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you need to simplify or combine overlapping ranges efficiently.

Sort intervals by start time, then merge by extending or adding intervals in one pass.

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