Merge Overlapping Intervals in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging intervals with overlapping pairs

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

DSA C#

using System;
using System.Collections.Generic;

public class Program {
    public static List<int[]> MergeIntervals(List<int[]> intervals) {
        intervals.Sort((a, b) => a[0].CompareTo(b[0]));
        List<int[]> merged = new List<int[]>();
        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[merged.Count - 1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[merged.Count - 1][1] = Math.Max(merged[merged.Count - 1][1], interval[1]);
            }
        }
        return merged;
    }

    public static void Main() {
        var intervals = new List<int[]> {
            new int[] {1, 3},
            new int[] {2, 6},
            new int[] {8, 10},
            new int[] {15, 18}
        };
        var result = MergeIntervals(intervals);
        foreach (var interval in result) {
            Console.Write($"{interval[0]}->{interval[1]} ");
        }
    }
}

A 1->6 8->10 15->18

B 1->6 2->6 8->10 15->18

C 1->3 2->6 8->10 15->18

D 1->3 8->10 15->18

💡 Hint

Think about how intervals that overlap are combined into one.

The code sorts intervals by start time. It merges intervals if they overlap by updating the end time of the last merged interval. Here, [1,3] and [2,6] overlap and merge into [1,6]. Others remain separate.

❓ Predict Output

intermediate

Result after merging intervals with nested overlaps

What will be printed after merging these intervals?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int[]> Merge(List<int[]> intervals) {
        intervals.Sort((a,b) => a[0].CompareTo(b[0]));
        List<int[]> merged = new List<int[]>();
        foreach(var interval in intervals) {
            if(merged.Count == 0 || merged[merged.Count-1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[merged.Count-1][1] = Math.Max(merged[merged.Count-1][1], interval[1]);
            }
        }
        return merged;
    }

    static void Main() {
        var intervals = new List<int[]> {
            new int[] {1, 4},
            new int[] {4, 5}
        };
        var merged = Merge(intervals);
        foreach(var i in merged) {
            Console.Write($"{i[0]}->{i[1]} ");
        }
    }
}

A 1->4

B 1->4 4->5

C 4->5

D 1->5

💡 Hint

Check if touching intervals are merged.

Intervals [1,4] and [4,5] touch at 4, so they merge into [1,5].

🔧 Debug

advanced

Identify the runtime error in interval merging code

What runtime error will this code produce when merging intervals?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int[]> Merge(List<int[]> intervals) {
        intervals.Sort((a,b) => a[0].CompareTo(b[0]));
        List<int[]> merged = new List<int[]>();
        foreach(var interval in intervals) {
            if(merged.Count == 0 || merged[merged.Count][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[merged.Count-1][1] = Math.Max(merged[merged.Count-1][1], interval[1]);
            }
        }
        return merged;
    }

    static void Main() {
        var intervals = new List<int[]> {
            new int[] {1, 3},
            new int[] {2, 4}
        };
        var merged = Merge(intervals);
        foreach(var i in merged) {
            Console.Write($"{i[0]}->{i[1]} ");
        }
    }
}

A NullReferenceException

B No error, outputs: 1->4

C IndexOutOfRangeException

D InvalidOperationException

💡 Hint

Check the index used to access the last element in the list.

The code uses merged[merged.Count] which is out of range since list indices go from 0 to Count-1.

🧠 Conceptual

advanced

Understanding time complexity of merging intervals

What is the time complexity of merging N intervals using the standard sorting and merging approach?

A O(N log N)

B O(N^2)

C O(N)

D O(log N)

💡 Hint

Consider the cost of sorting and then merging.

Sorting intervals takes O(N log N). Merging them in one pass takes O(N). Overall complexity is O(N log N).

🚀 Application

expert

Final merged intervals after multiple merges

Given the following intervals, what is the final merged list printed by the code?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static List<int[]> Merge(List<int[]> intervals) {
        intervals.Sort((a,b) => a[0].CompareTo(b[0]));
        List<int[]> merged = new List<int[]>();
        foreach(var interval in intervals) {
            if(merged.Count == 0 || merged[merged.Count-1][1] < interval[0]) {
                merged.Add(interval);
            } else {
                merged[merged.Count-1][1] = Math.Max(merged[merged.Count-1][1], interval[1]);
            }
        }
        return merged;
    }

    static void Main() {
        var intervals = new List<int[]> {
            new int[] {1, 4},
            new int[] {2, 5},
            new int[] {7, 9},
            new int[] {8, 10},
            new int[] {12, 15},
            new int[] {14, 18}
        };
        var merged = Merge(intervals);
        foreach(var i in merged) {
            Console.Write($"{i[0]}->{i[1]} ");
        }
    }
}

A 1->5 7->9 12->18

B 1->5 7->10 12->18

C 1->4 2->5 7->9 8->10 12->15 14->18

D 1->5 7->10 12->15

💡 Hint

Merge intervals step by step, combining overlapping ones.

Intervals [1,4] and [2,5] merge to [1,5]. Intervals [7,9] and [8,10] merge to [7,10]. Intervals [12,15] and [14,18] merge to [12,18].

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