Non Overlapping Intervals Minimum Removal in DSA C# - Execution Trace

Concept Flow - Non Overlapping Intervals Minimum Removal

Sort intervals by end time

↓

Initialize count=0, prev_end = -∞

↓

For each interval

↓

Check if interval start >= prev_end?

No→Remove interval, count++

Yes↓

Update prev_end = current interval end

↓

Repeat for all intervals

↓

Return count

Sort intervals by their end time, then iterate to count how many intervals must be removed to avoid overlaps.

Execution Sample

DSA C#

int EraseOverlapIntervals(int[][] intervals) {
  Array.Sort(intervals, (a,b) => a[1].CompareTo(b[1]));
  int count = 0, prevEnd = int.MinValue;
  foreach(var interval in intervals) {
    if(interval[0] < prevEnd) count++;
    else prevEnd = interval[1];
  }
  return count;
}

This code counts the minimum number of intervals to remove so that no intervals overlap.

Execution Table

Step	Operation	Current Interval	prevEnd	Count Removed	Visual State
1	Sort intervals by end time	[1,2], [2,3], [3,4], [1,3]	-	0	[1,2] -> [1,3] -> [2,3] -> [3,4] (sorted by end)
2	Initialize prevEnd and count	-	−∞	0	Empty processed list
3	Check interval start < prevEnd?	[1,2]	−∞	0	[1,2] selected, prevEnd updated to 2
4	Check interval start < prevEnd?	[1,3]	2	0	1 < 2 is True, remove interval, count=1
5	Check interval start < prevEnd?	[2,3]	2	1	2 < 2 is False, prevEnd updated to 3
6	Check interval start < prevEnd?	[3,4]	3	1	3 < 3 is False, prevEnd updated to 4
7	End of intervals	-	4	1	Final count = 1

💡 All intervals processed; minimum removal count is 1

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
prevEnd	−∞	2	2	3	4	4
count	0	0	1	1	1	1

Key Moments - 3 Insights

Why do we sort intervals by their end time?

Sorting by end time ensures we always keep the interval that finishes earliest, allowing more intervals to fit without overlap (see Step 1 in execution_table).

Why do we compare interval start with prevEnd instead of end?

We compare the current interval's start with prevEnd to check if it overlaps with the last kept interval (Step 4-6). If start < prevEnd, it overlaps and must be removed.

Why do we update prevEnd only when interval is not removed?

Updating prevEnd only when we keep an interval ensures prevEnd always marks the end of the last non-overlapping interval (Step 5 and 6).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what happens when interval [1,3] is checked?

A Interval is kept and prevEnd updated to 3

B Interval overlaps and is removed, count increases to 1

C Interval does not overlap, count remains 0

D prevEnd is reset to −∞

💡 Hint

See Step 4 in execution_table where count changes from 0 to 1 due to overlap

At which step does prevEnd get updated to 4?

A Step 5

B Step 4

C Step 6

D Step 3

💡 Hint

Check variable_tracker and execution_table Step 6 where prevEnd changes to 4

If the intervals were not sorted by end time, what would likely happen?

A The count of removals might be incorrect

B The algorithm would run faster

C prevEnd would always be −∞

D No intervals would be removed

💡 Hint

Refer to Step 1 in execution_table showing sorting is crucial for correctness

Concept Snapshot

Non Overlapping Intervals Minimum Removal:
- Sort intervals by end time
- Initialize count=0, prevEnd = -∞
- For each interval:
  - If start < prevEnd, remove it (count++)
  - Else update prevEnd = interval end
- Return count of removals
This greedy approach keeps max intervals without overlap.

Full Transcript

To find the minimum number of intervals to remove so that no intervals overlap, first sort all intervals by their end time. Then, start with a count of zero removals and a prevEnd set to negative infinity. Iterate through each interval: if the start of the current interval is less than prevEnd, it means it overlaps with the last kept interval, so increment the removal count. Otherwise, update prevEnd to the end of the current interval. After processing all intervals, the count will represent the minimum removals needed. This method ensures we keep intervals that finish earliest, maximizing the number of non-overlapping intervals.

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