Insert Interval into Sorted List in DSA C#

Mental Model

We add a new time slot into a list of sorted time slots, merging any that overlap so the list stays neat and ordered.

Analogy: Imagine you have a schedule with booked meetings sorted by time. You want to add a new meeting. If it overlaps with existing ones, you combine them into one longer meeting so no times clash.

Intervals: [1,3] -> [6,9] -> null
Insert: [2,5]
Goal: merge overlapping intervals and keep order

Dry Run Walkthrough

Input: intervals: [1,3] -> [6,9], insert [2,5]

Goal: Insert [2,5] into the sorted list and merge overlapping intervals to keep the list sorted and non-overlapping.

Step 1: Start with empty result list and i=0. First interval [1,3].end=3 not < insert.start=2, so no intervals added before.

Result: null
Current intervals: [1,3] -> [6,9] -> null
Insert: [2,5]
i=0

Why: We need to process intervals before the new one that do not overlap.

Step 2: Merge loop: i=0, [1,3].start=1 <= insert.end=5, yes. Update insert to [min(2,1)=1, max(5,3)=5]=[1,5], i=1

Result: null
Current intervals: [6,9] -> null
Insert: [1,5]
i=1

Why: [1,3] overlaps with insert since it does not end before insert starts, so merge it.

Step 3: Merge loop: i=1, [6,9].start=6 > insert.end=5, no overlap, exit merge loop

Result: null
Current intervals: [6,9] -> null
Insert: [1,5]
i=1

Why: Stop merging when next interval starts after current merged end.

Step 4: Add merged insert [1,5] to result

Result: [1,5] -> null
Current intervals: [6,9] -> null
Insert: null
i=1

Why: After merging all overlaps, add the merged interval.

Step 5: Add remaining intervals [6,9] to result

Result: [1,5] -> [6,9] -> null
Current intervals: null
i=2

Why: Append all intervals after the merged one.

Result:

Final intervals: [1,5] -> [6,9] -> null

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> InsertInterval(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new List<Interval>();
        int i = 0;
        // Add all intervals ending before newInterval starts
        while (i < intervals.Count && intervals[i].end < newInterval.start) {
            result.Add(intervals[i]);
            i++;
        }
        // Merge overlapping intervals
        while (i < intervals.Count && intervals[i].start <= newInterval.end) {
            newInterval.start = Math.Min(newInterval.start, intervals[i].start);
            newInterval.end = Math.Max(newInterval.end, intervals[i].end);
            i++;
        }
        // Add merged interval
        result.Add(newInterval);
        // Add remaining intervals
        while (i < intervals.Count) {
            result.Add(intervals[i]);
            i++;
        }
        return result;
    }

    public static void Main() {
        List<Interval> intervals = new List<Interval> {
            new Interval(1,3),
            new Interval(6,9)
        };
        Interval newInterval = new Interval(2,5);
        List<Interval> result = InsertInterval(intervals, newInterval);
        foreach (var interval in result) {
            Console.Write(interval + " -> ");
        }
        Console.WriteLine("null");
    }
}

while (i < intervals.Count && intervals[i].end < newInterval.start) {

Add intervals that end before new interval starts to result

while (i < intervals.Count && intervals[i].start <= newInterval.end) {

Merge all intervals overlapping with new interval

newInterval.start = Math.Min(newInterval.start, intervals[i].start);

Update new interval start to earliest overlapping start

newInterval.end = Math.Max(newInterval.end, intervals[i].end);

Update new interval end to latest overlapping end

result.Add(newInterval);

Add merged new interval to result

while (i < intervals.Count) {

Add remaining intervals after merged new interval

Output

[1,5] -> [6,9] -> null

Complexity Analysis

Time: O(n) because we scan through the list of intervals once

Space: O(n) because we create a new list to store the merged intervals

vs Alternative: Compared to inserting and merging in place which can be complex, this approach is simpler and efficient with linear time and space.

Edge Cases

Empty intervals list

The new interval is simply added as the only interval

DSA C#

while (i < intervals.Count && intervals[i].end < newInterval.start) {

New interval does not overlap and goes at the end

All intervals are added first, then new interval is appended

DSA C#

while (i < intervals.Count && intervals[i].end < newInterval.start) {

New interval overlaps all existing intervals

All intervals are merged into one big interval

DSA C#

while (i < intervals.Count && intervals[i].start <= newInterval.end) {

When to Use This Pattern

When you see a problem about adding a new time range into sorted ranges and merging overlaps, use the Insert Interval pattern to merge efficiently.

Common Mistakes

Mistake: Adding the new interval before merging overlapping intervals
Fix: First merge all overlapping intervals with the new one, then add the merged interval

Mistake: Not handling intervals that come after the new interval
Fix: After merging, add all remaining intervals to the result list

Summary

Inserts a new interval into a sorted list and merges overlapping intervals.

Use when you need to add a time slot into sorted, non-overlapping intervals.

Merge all overlapping intervals first before adding the new combined interval.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To sort the intervals again after insertion without merging

B. To add the new interval at the end without checking overlaps

C. To remove all intervals that come before the new interval

D. To merge overlapping intervals and keep the list sorted without overlaps

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Identify the required action

   We must merge any overlapping intervals with the new one and keep the list sorted without overlaps.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted without overlaps -> Option D

4. Quick Check:

   Insert and merge intervals = To merge overlapping intervals and keep the list sorted without overlaps [OK]

Hint: Merge overlapping intervals to keep list sorted and non-overlapping [OK]

Common Mistakes:

• Inserting without merging overlaps
• Appending without sorting
• Removing unrelated intervals

2. Which of the following C# code snippets correctly declares a list of intervals as List intervals?

easy

A. var intervals = new List { [1, 3], [6, 9] };

B. var intervals = new List { new int[] {1, 3}, new int[] {6, 9} };

C. List intervals = new List { (1, 3), (6, 9) };

D. List<int> intervals = new List<int> { {1, 3}, {6, 9} };

Solution

1. Step 1: Check correct syntax for List of int arrays

   List requires elements as int arrays, declared with new int[] {start, end}.

2. Step 2: Validate each option

   var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; uses new int[] correctly; others use invalid syntax like braces or tuples.

3. Final Answer:

   var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; -> Option B

4. Quick Check:

   List of int arrays syntax = var intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; [OK]

Hint: Use new int[] {start, end} inside List initialization [OK]

Common Mistakes:

• Using curly braces instead of new int[]
• Using tuples instead of arrays
• Incorrect variable type declaration

3. Given the intervals [[1, 3], [6, 9]] and a new interval [2, 5], what is the resulting list after inserting and merging?

medium

A. [[2, 5], [6, 9]]

B. [[1, 3], [2, 5], [6, 9]]

C. [[1, 5], [6, 9]]

D. [[1, 9]]

Solution

1. Step 1: Identify overlapping intervals

   The new interval [2, 5] overlaps with [1, 3] because 2 ≤ 3.

2. Step 2: Merge overlapping intervals

   Merge [1, 3] and [2, 5] into [1, 5]. The interval [6, 9] remains unchanged.

3. Final Answer:

   [[1, 5], [6, 9]] -> Option C

4. Quick Check:

   Merged intervals = [[1, 5], [6, 9]] [OK]

Hint: Merge intervals if new start ≤ existing end [OK]

Common Mistakes:

• Not merging overlapping intervals
• Inserting new interval without merging
• Merging all intervals incorrectly

4. Consider this C# code snippet to insert an interval into a sorted list. What is the bug?

var intervals = new List { new int[] {1, 2}, new int[] {3, 5} };
var newInterval = new int[] {4, 7};

foreach(var interval in intervals) {
    if(interval[1] >= newInterval[0]) {
        interval[1] = Math.Max(interval[1], newInterval[1]);
        break;
    }
}

medium

A. It modifies only the first overlapping interval but misses merging subsequent overlaps

B. It throws a runtime exception due to invalid index access

C. It inserts the new interval at the wrong position

D. It does not check for any overlaps before merging

Solution

1. Step 1: Analyze the loop behavior

   The loop breaks after merging with the first overlapping interval, ignoring others.

2. Step 2: Identify the bug impact

   Intervals after the first overlap are not merged, causing incorrect final intervals.

3. Final Answer:

   It modifies only the first overlapping interval but misses merging subsequent overlaps -> Option A

4. Quick Check:

   Loop breaks early, missing merges = It modifies only the first overlapping interval but misses merging subsequent overlaps [OK]

Hint: Do not break loop early; merge all overlapping intervals [OK]

Common Mistakes:

• Breaking loop too soon
• Not merging all overlaps
• Assuming single overlap only

5. You have intervals [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] and a new interval [4, 8]. After inserting and merging, what is the final list?

hard

A. [[1, 2], [3, 10], [12, 16]]

B. [[1, 2], [4, 8], [12, 16]]

C. [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]

D. [[1, 2], [3, 8], [12, 16]]

Solution

1. Step 1: Find intervals overlapping with [4, 8]

   Intervals [3, 5], [6, 7], and [8, 10] overlap with [4, 8].

2. Step 2: Merge all overlapping intervals

   Merge [3, 5], [6, 7], [8, 10], and [4, 8] into [3, 10].

3. Step 3: Keep non-overlapping intervals unchanged

   Intervals [1, 2] and [12, 16] remain as is.

4. Final Answer:

   [[1, 2], [3, 10], [12, 16]] -> Option A

5. Quick Check:

   Merged overlapping intervals correctly = [[1, 2], [3, 10], [12, 16]] [OK]

Hint: Merge all intervals overlapping new interval into one [OK]

Common Mistakes:

• Merging only some overlapping intervals
• Not merging intervals that touch at boundaries
• Replacing intervals instead of merging