Insert Interval into Sorted List in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting an interval that merges with one existing interval

What is the output list of intervals after inserting [4, 8] into the sorted list [[1, 3], [6, 9]]?

DSA C#

List<int[]> intervals = new List<int[]> { new int[] {1, 3}, new int[] {6, 9} };
int[] newInterval = new int[] {4, 8};
var result = InsertInterval(intervals, newInterval);
foreach(var interval in result) {
    Console.Write($"[{interval[0]}, {interval[1]}] ");
}

List<int[]> InsertInterval(List<int[]> intervals, int[] newInterval) {
    List<int[]> result = new List<int[]>();
    int i = 0;
    while (i < intervals.Count && intervals[i][1] < newInterval[0]) {
        result.Add(intervals[i]);
        i++;
    }
    while (i < intervals.Count && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.Add(newInterval);
    while (i < intervals.Count) {
        result.Add(intervals[i]);
        i++;
    }
    return result;
}

A [[1, 3], [4, 9]]

B [[4, 8], [6, 9]]

C [[1, 9]]

D [[1, 3], [4, 8], [6, 9]]

💡 Hint

Think about how overlapping intervals merge into one.

The new interval [4,8] overlaps with [6,9], so they merge into [4,9]. The first interval [1,3] does not overlap and stays separate.

❓ Predict Output

intermediate

Output after inserting an interval that does not overlap any existing intervals

What is the output list of intervals after inserting [10, 12] into the sorted list [[1, 5], [6, 9]]?

DSA C#

List<int[]> intervals = new List<int[]> { new int[] {1, 5}, new int[] {6, 9} };
int[] newInterval = new int[] {10, 12};
var result = InsertInterval(intervals, newInterval);
foreach(var interval in result) {
    Console.Write($"[{interval[0]}, {interval[1]}] ");
}

List<int[]> InsertInterval(List<int[]> intervals, int[] newInterval) {
    List<int[]> result = new List<int[]>();
    int i = 0;
    while (i < intervals.Count && intervals[i][1] < newInterval[0]) {
        result.Add(intervals[i]);
        i++;
    }
    while (i < intervals.Count && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.Add(newInterval);
    while (i < intervals.Count) {
        result.Add(intervals[i]);
        i++;
    }
    return result;
}

A [[1, 5], [6, 9], [10, 12]]

B [[1, 5], [6, 9]]

C [[10, 12], [1, 5], [6, 9]]

D [[1, 12]]

💡 Hint

New interval is after all existing intervals, so it should be added at the end.

Since [10,12] does not overlap and is after all intervals, it is simply appended.

🔧 Debug

advanced

Identify the error in interval insertion code

What error will this code produce when inserting [2, 5] into [[1, 3], [6, 9]]? List intervals = new List { new int[] {1, 3}, new int[] {6, 9} }; int[] newInterval = new int[] {2, 5}; var result = InsertInterval(intervals, newInterval); List InsertInterval(List intervals, int[] newInterval) { List result = new List(); int i = 0; while (i < intervals.Count && intervals[i][1] <= newInterval[0]) { result.Add(intervals[i]); i++; } while (i < intervals.Count && intervals[i][0] < newInterval[1]) { newInterval[0] = Math.Min(newInterval[0], intervals[i][0]); newInterval[1] = Math.Max(newInterval[1], intervals[i][1]); i++; } result.Add(newInterval); while (i < intervals.Count) { result.Add(intervals[i]); i++; } return result; }

A No error, output: [[1, 5], [6, 9]]

B Output: [[1, 3], [2, 5], [6, 9]] (incorrect merging)

C Infinite loop due to incorrect loop condition

D Output: [[1, 5], [6, 9]] but misses some intervals

💡 Hint

Check the loop conditions carefully for merging intervals.

The conditions use <= and < incorrectly, causing partial merges and incorrect output.

❓ Predict Output

advanced

Output after inserting an interval that merges multiple existing intervals

What is the output list of intervals after inserting [2, 7] into the sorted list [[1, 3], [4, 6], [8, 10]]?

DSA C#

List<int[]> intervals = new List<int[]> { new int[] {1, 3}, new int[] {4, 6}, new int[] {8, 10} };
int[] newInterval = new int[] {2, 7};
var result = InsertInterval(intervals, newInterval);
foreach(var interval in result) {
    Console.Write($"[{interval[0]}, {interval[1]}] ");
}

List<int[]> InsertInterval(List<int[]> intervals, int[] newInterval) {
    List<int[]> result = new List<int[]>();
    int i = 0;
    while (i < intervals.Count && intervals[i][1] < newInterval[0]) {
        result.Add(intervals[i]);
        i++;
    }
    while (i < intervals.Count && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
        i++;
    }
    result.Add(newInterval);
    while (i < intervals.Count) {
        result.Add(intervals[i]);
        i++;
    }
    return result;
}

A [[1, 10]]

B [[1, 3], [2, 7], [8, 10]]

C [[1, 6], [2, 7], [8, 10]]

D [[1, 7], [8, 10]]

💡 Hint

The new interval overlaps with two intervals, so they merge into one.

Intervals [1,3] and [4,6] overlap with [2,7], merging into [1,7]. The last interval stays separate.

🧠 Conceptual

expert

Minimum number of intervals after inserting and merging

Given a sorted list of non-overlapping intervals and a new interval to insert, what is the minimum number of intervals possible after insertion and merging?

A At least the original number of intervals

B At most the original number of intervals

C At most the original number of intervals plus one

D At least the original number of intervals minus one

💡 Hint

Consider if the new interval overlaps with none, one, or multiple intervals.

Inserting a new interval can add one new interval if no overlaps occur, or merge multiple intervals reducing count. So the maximum is original count plus one.

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