Non Overlapping Intervals Minimum Removal in DSA C#

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping the interval that ends earliest to leave room for others.

Analogy: Imagine scheduling meetings in one room. To fit the most meetings without clashes, always pick the meeting that finishes earliest, then schedule the next meeting that starts after it ends.

Intervals: [1,3] -> [2,4] -> [3,5] -> null
Goal: Remove minimum intervals so none overlap

Dry Run Walkthrough

Input: intervals: [1,3], [2,4], [3,5]

Goal: Remove the fewest intervals so that no two intervals overlap

Step 1: Sort intervals by end time

[1,3] -> [2,4] -> [3,5]

Why: Sorting by end time helps us pick intervals that finish earliest first

Step 2: Keep first interval [1,3], set end = 3

[1,3] ↑ (end=3) -> [2,4] -> [3,5]

Why: Start with the earliest finishing interval to maximize room for others

Step 3: Check [2,4]: start 2 < end 3 -> overlap, remove it

[1,3] ↑ (end=3) -> [2,4] (removed) -> [3,5]

Why: This interval overlaps with the kept one, so remove it

Step 4: Check [3,5]: start 3 >= end 3 -> keep it, update end = 5

[1,3] -> [3,5] ↑ (end=5)

Why: No overlap, so keep and update end to this interval's end

Result:

[1,3] -> [3,5] -> null
Minimum removals = 1

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 class Solution {
    public int EraseOverlapIntervals(List<Interval> intervals) {
        if (intervals.Count == 0) return 0;
        intervals.Sort((a, b) => a.end.CompareTo(b.end));
        int end = intervals[0].end;
        int count = 0;
        for (int i = 1; i < intervals.Count; i++) {
            if (intervals[i].start < end) {
                count++;
            } else {
                end = intervals[i].end;
            }
        }
        return count;
    }

    public static void Main() {
        var intervals = new List<Interval> {
            new Interval(1,3),
            new Interval(2,4),
            new Interval(3,5)
        };
        var sol = new Solution();
        int removals = sol.EraseOverlapIntervals(intervals);
        Console.WriteLine($"Minimum removals = {removals}");
    }
}

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

Sort intervals by their end time to prioritize earliest finishing

int end = intervals[0].end;

Initialize end to the end of the first interval kept

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

Traverse remaining intervals to check for overlaps

if (intervals[i].start < end) { count++; }

If current interval starts before end, it overlaps and must be removed

else { end = intervals[i].end; }

If no overlap, update end to current interval's end

Output

Minimum removals = 1

Complexity Analysis

Time: O(n log n) because we sort the intervals first, then traverse them once

Space: O(1) because sorting is in-place and only a few variables are used

vs Alternative: Naive approach checks all pairs for overlap O(n^2), this greedy method is faster

Edge Cases

empty list

returns 0 removals since no intervals exist

DSA C#

if (intervals.Count == 0) return 0;

all intervals non-overlapping

returns 0 removals because no overlaps

DSA C#

if (intervals[i].start < end) { count++; }

all intervals fully overlapping

removes all but one interval

DSA C#

if (intervals[i].start < end) { count++; }

When to Use This Pattern

When asked to remove minimum intervals to avoid overlaps, use a greedy approach sorting by end times to keep earliest finishing intervals.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to correctly apply the greedy strategy

Mistake: Updating end pointer incorrectly when removing intervals
Fix: Only update end when keeping an interval, not when removing

Summary

Removes the fewest intervals so that no intervals overlap.

Use when you want to schedule intervals without clashes by removing minimum intervals.

Always keep the interval that ends earliest to maximize space for others.

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