Non Overlapping Intervals Minimum Removal in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Interval Removals Calculation

What is the output of the following C# code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA C#

using System;
using System.Collections.Generic;

public class Solution {
    public int EraseOverlapIntervals(int[][] intervals) {
        if (intervals.Length == 0) return 0;
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        int count = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] < end) {
                count++;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }
}

public class Program {
    public static void Main() {
        int[][] intervals = new int[][] {
            new int[] {1, 3},
            new int[] {2, 4},
            new int[] {3, 5},
            new int[] {6, 7}
        };
        Solution sol = new Solution();
        Console.WriteLine(sol.EraseOverlapIntervals(intervals));
    }
}

A 3

B 2

C 1

D 0

💡 Hint

Sort intervals by their end time and count overlaps.

The code sorts intervals by their end time and counts how many intervals overlap with the previous chosen interval. Only one interval needs to be removed to avoid overlaps.

🧠 Conceptual

intermediate

Understanding the Greedy Choice in Interval Removal

Why does sorting intervals by their end time help in minimizing the number of intervals to remove to avoid overlaps?

A Because sorting by end time groups overlapping intervals together.

B Because sorting by start time always leads to minimum removals.

C Because sorting by interval length guarantees minimal removals.

D Because choosing intervals with earliest end time leaves more room for following intervals.

💡 Hint

Think about how choosing intervals that finish earlier affects the rest.

Choosing intervals with the earliest end time allows more intervals to fit after it without overlapping, minimizing removals.

🔧 Debug

advanced

Identify the Bug in Interval Removal Code

What error will the following code produce when run, and why?

DSA C#

public int EraseOverlapIntervals(int[][] intervals) {
    Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
    int count = 0;
    int end = intervals[0][1];
    for (int i = 1; i < intervals.Length; i++) {
        if (intervals[i][0] < end) {
            count++;
        } else {
            end = intervals[i][1];
        }
    }
    return count;
}

A NullReferenceException due to uninitialized array

B IndexOutOfRangeException if intervals is empty

C No error, returns correct result

D InvalidOperationException from Array.Sort

💡 Hint

Consider what happens if intervals array is empty.

If intervals is empty, accessing intervals[0] causes IndexOutOfRangeException.

❓ Predict Output

advanced

Output of Interval Removal with Nested Intervals

What is the output of the following code for nested intervals?

DSA C#

int[][] intervals = new int[][] {
    new int[] {1, 10},
    new int[] {2, 3},
    new int[] {4, 5},
    new int[] {6, 7},
    new int[] {8, 9}
};

Solution sol = new Solution();
Console.WriteLine(sol.EraseOverlapIntervals(intervals));

A 1

B 2

C 3

D 4

💡 Hint

The large interval overlaps with all smaller intervals inside it.

After sorting by end time, the greedy algorithm selects the four small non-overlapping intervals [2,3], [4,5], [6,7], [8,9] and removes the large [1,10], resulting in 1 removal.

🚀 Application

expert

Minimum Removals for Overlapping Intervals with Same End Time

Given intervals with some having the same end time, what is the minimum number of intervals to remove?

DSA C#

int[][] intervals = new int[][] {
    new int[] {1, 3},
    new int[] {2, 3},
    new int[] {3, 4},
    new int[] {3, 4},
    new int[] {4, 5}
};

Solution sol = new Solution();
Console.WriteLine(sol.EraseOverlapIntervals(intervals));

A 2

B 1

C 3

D 0

💡 Hint

Intervals with same end time can cause overlaps if start times overlap.

Intervals [1,3] and [2,3] overlap, and [3,4] duplicates overlap. Minimum removals is 2.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To sort intervals by their start time

B. To remove the minimum number of intervals so that the remaining intervals do not overlap

C. To merge all intervals into one big interval

D. To find the maximum number of overlapping intervals

Solution

1. Step 1: Understand the problem goal

   The problem asks to remove as few intervals as possible so that no two intervals overlap.

2. Step 2: Clarify what non-overlapping means

   Non-overlapping means for any two intervals, one ends before the other starts.

3. Final Answer:

   To remove the minimum number of intervals so that the remaining intervals do not overlap -> Option B

4. Quick Check:

   Minimum removal = no overlaps [OK]

Hint: Focus on removing intervals, not merging or counting overlaps [OK]

Common Mistakes:

• Thinking the goal is to merge intervals
• Confusing maximum overlap with minimum removal
• Sorting intervals without removing any

2. Which of the following C# code snippets correctly sorts intervals by their end time for the minimum removal problem?

easy

A. Array.Sort(intervals, (a, b) => b[1].CompareTo(a[1]));

B. Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

C. Array.Sort(intervals, (a, b) => b[0].CompareTo(a[0]));

D. Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));

Solution

1. Step 1: Identify sorting criteria for minimum removal

   We sort intervals by their end time ascending to greedily keep intervals that finish earliest.

2. Step 2: Match code to sorting by end time ascending

   Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1])); uses a[1].CompareTo(b[1]) which sorts by end time ascending correctly.

3. Final Answer:

   Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1])); -> Option D

4. Quick Check:

   Sort by end time ascending = Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1])); [OK]

Hint: Sort intervals by end time ascending for greedy approach [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Sorting in descending order by mistake
• Using wrong array indices for comparison

3. What is the output of the following C# code snippet?

int[][] intervals = new int[][] {
  new int[] {1, 3},
  new int[] {2, 4},
  new int[] {3, 5}
};

Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));

int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++) {
  if (intervals[i][0] < end) {
    count++;
  } else {
    end = intervals[i][1];
  }
}
Console.WriteLine(count);

medium

A. 1

B. 2

C. 0

D. 3

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals by end: [1,3], [2,4], [3,5]

2. Step 2: Count overlaps by comparing start with current end

   Check intervals: - i=1: start=2 < end=3 -> overlap, count=1 - i=2: start=3 < end=3? No, update end=5

3. Final Answer:

   1 -> Option A

4. Quick Check:

   One overlap counted = 1 [OK]

Hint: Count intervals starting before current end to find removals [OK]

Common Mistakes:

• Not updating end when no overlap
• Counting intervals that do not overlap
• Sorting incorrectly before loop

4. Identify the bug in the following C# code for minimum interval removal:

int[][] intervals = new int[][] {
  new int[] {1, 2},
  new int[] {1, 3},
  new int[] {2, 4}
};

Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++) {
  if (intervals[i][0] < end) {
    count++;
  } else {
    end = intervals[i][1];
  }
}
Console.WriteLine(count);

medium

A. Sorting by start time instead of end time causes incorrect removal count

B. Not initializing count to 1 causes wrong output

C. Loop should start from i = 0 instead of i = 1

D. Using intervals[i][0] instead of intervals[i][1] in comparison

Solution

1. Step 1: Check sorting criteria

   The code sorts intervals by start time, but greedy approach requires sorting by end time.

2. Step 2: Understand impact on counting removals

   Sorting by start time can cause wrong overlaps detection and incorrect count.

3. Final Answer:

   Sorting by start time instead of end time causes incorrect removal count -> Option A

4. Quick Check:

   Sort by end time needed, not start time [OK]

Hint: Always sort by end time ascending for correct greedy removal [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Starting loop at wrong index
• Confusing interval start and end in comparisons

5. Given intervals [[1,2],[2,3],[3,4],[1,3]], what is the minimum number of intervals to remove to make the rest non-overlapping?

hard

A. 0

B. 2

C. 1

D. 3

Solution

1. Step 1: Sort intervals by end time ascending

   Sorted intervals: [1,2], [1,3], [2,3], [3,4]

2. Step 2: Count overlaps and removals

   Start with end=2 (from [1,2]) - [1,3]: start=1 < end=2 overlap, count=1 - [2,3]: start=2 <= end=2 no overlap, update end=3 - [3,4]: start=3 <= end=3 no overlap, update end=4 Total removals = 1

3. Step 3: Re-check for minimal removals

   Check if removing [1,3] is enough. Yes, only 1 removal needed.

4. Final Answer:

   1 -> Option C

5. Quick Check:

   Remove overlapping [1,3] only = 1 [OK]

Hint: Sort by end time, greedily keep intervals with earliest end [OK]

Common Mistakes:

• Counting all overlapping intervals instead of minimal removals
• Not sorting intervals before processing
• Confusing intervals with same start or end times