Non Overlapping Intervals Minimum Removal in DSA Typescript - Execution Trace

Concept Flow - Non Overlapping Intervals Minimum Removal

Sort intervals by end time

↓

Initialize count=0, prevEnd = -∞

↓

For each interval

↓

Check if current start >= prevEnd?

No→Remove interval, count++

Yes↓

Update prevEnd = current 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 Typescript

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0, prevEnd = -Infinity;
  for (const [start, end] of intervals) {
    if (start >= prevEnd) prevEnd = end;
    else count++;
  }
  return count;
}

This code sorts intervals by end time and counts how many intervals overlap and must be removed.

Execution Table

Step	Operation	Current Interval	prevEnd	Count	Action	Visual State
1	Sort intervals	[1,2], [2,3], [3,4], [1,3]	-∞	0	Sorted by end time	[1,2] -> [2,3] -> [1,3] -> [3,4]
2	Initialize	-	-∞	0	Set prevEnd = -∞, count = 0	[1,2] -> [2,3] -> [1,3] -> [3,4]
3	Check interval	[1,2]	-∞	0	1 >= -∞ true, update prevEnd=2	[1,2] -> [2,3] -> [1,3] -> [3,4]
4	Check interval	[2,3]	2	0	2 >= 2 true, update prevEnd=3	[1,2] -> [2,3] -> [1,3] -> [3,4]
5	Check interval	[1,3]	3	0	1 >= 3 false, remove interval, count=1	[1,2] -> [2,3] -> [3,4]
6	Check interval	[3,4]	3	1	3 >= 3 true, update prevEnd=4	[1,2] -> [2,3] -> [3,4]
7	End	-	4	1	All intervals processed	[1,2] -> [2,3] -> [3,4]

💡 All intervals checked, minimum removal count is 1

Variable Tracker

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

Key Moments - 3 Insights

Why do we sort intervals by their end time instead of start time?

Sorting by end time ensures we always pick the interval that finishes earliest, leaving more room for following intervals. This is shown in execution_table step 1 where intervals are sorted by end time.

Why do we update prevEnd only when current start >= prevEnd?

We update prevEnd to the current interval's end only if it doesn't overlap (start >= prevEnd). Otherwise, we remove the interval and keep prevEnd unchanged. See execution_table steps 3-6 for this logic.

Why do we increment count when start < prevEnd?

When start < prevEnd, intervals overlap, so we must remove one. We increment count to track removals. This happens at step 5 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of prevEnd?

A 2

B 3

C -∞

D 4

💡 Hint

Check the 'prevEnd' column at step 4 in execution_table

At which step does the count increment indicating an interval removal?

A Step 3

B Step 6

C Step 5

D Step 7

💡 Hint

Look for 'remove interval, count=1' in the Action column of execution_table

If intervals were not sorted by end time, how would the visual state change at step 2?

A Intervals would be in original order, possibly causing more removals

B Intervals would be sorted by start time, same result

C Intervals would be reversed, fewer removals

D No change in intervals order

💡 Hint

Refer to execution_table step 1 showing sorted intervals

Concept Snapshot

Non Overlapping Intervals Minimum Removal:
- Sort intervals by end time
- Initialize count=0, prevEnd=-∞
- For each interval:
  - If start >= prevEnd, update prevEnd
  - Else increment count (remove interval)
- Return count as minimum removals

Full Transcript

To find the minimum number of intervals to remove so that no intervals overlap, first sort the intervals by their end times. This allows us to always pick the interval that finishes earliest, maximizing space for others. Initialize a count for removals and a variable prevEnd to track the end of the last added interval. Iterate through each interval: if the current interval's start is greater or equal to prevEnd, update prevEnd to this interval's end. Otherwise, increment the removal count because the interval overlaps. After processing all intervals, the count reflects the minimum removals needed. This approach is efficient and greedy, ensuring the least removals.

Practice

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

easy

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

B. To find the maximum number of overlapping intervals

C. To merge all intervals into one large interval

D. To sort intervals by their start time

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 intervals do not share any common points except possibly touching ends.

3. Final Answer:

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

4. Quick Check:

   Minimum removal = non-overlapping intervals [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 TypeScript function signatures correctly represents a function to solve the Non Overlapping Intervals Minimum Removal problem?

easy

A. function eraseOverlapIntervals(intervals: string[][]): string

B. function eraseOverlapIntervals(intervals: number[]): number[]

C. function eraseOverlapIntervals(intervals: number[][]): number

D. function eraseOverlapIntervals(intervals: number[][]): void

Solution

1. Step 1: Identify input and output types

   The input is an array of intervals, each interval is an array of two numbers. The output is the count of intervals removed, a number.

2. Step 2: Match the correct signature

   function eraseOverlapIntervals(intervals: number[][]): number matches input as number[][] and output as number, which fits the problem.

3. Final Answer:

   function eraseOverlapIntervals(intervals: number[][]): number -> Option C

4. Quick Check:

   Input array of number arrays, output number [OK]

Hint: Input is array of number pairs, output is a number count [OK]

Common Mistakes:

• Using wrong input type like number[] instead of number[][]
• Returning array instead of number
• Using void return type

3. What is the output of the following TypeScript code?

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0;
  let end = -Infinity;
  for (const interval of intervals) {
    if (interval[0] >= end) {
      end = interval[1];
    } else {
      count++;
    }
  }
  return count;
}

console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]));

medium

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Sort intervals by end time

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

2. Step 2: Iterate and count removals

   Start with end = -Infinity
   Check [1,2]: 1 >= -Infinity true, end=2
   [2,3]: 2 >= 2 true, end=3
   [1,3]: 1 >= 3 false, count=1
   [3,4]: 3 >= 3 true, end=4

3. Final Answer:

   1 -> Option A

4. Quick Check:

   One interval removed to avoid overlap [OK]

Hint: Sort by end, count intervals starting before current end [OK]

Common Mistakes:

• Not sorting intervals by end time
• Counting intervals incorrectly when start equals end
• Confusing count of removals with count of intervals kept

4. Identify the bug in this TypeScript function for minimum interval removal:

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  let count = 0;
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < end) {
      count++;
    } else {
      end = intervals[i][1];
    }
  }
  return count;
}

medium

A. Initializing end with intervals[0][0] instead of intervals[0][1]

B. Sorting intervals by start time instead of end time causes incorrect removals

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

D. The function should return the count of intervals kept, not removed

Solution

1. Step 1: Check sorting criteria

   The function sorts intervals by start time, but the greedy approach requires sorting by end time to minimize removals.

2. Step 2: Understand impact on removal count

   Sorting by start time can cause incorrect counting of overlapping intervals, leading to wrong removal count.

3. Final Answer:

   Sorting intervals by start time instead of end time causes incorrect removals -> Option B

4. Quick Check:

   Sort by end time for correct minimum removal [OK]

Hint: Always sort intervals by end time for this problem [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Wrong initialization of end variable
• Incorrect loop start index

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

hard

A. 0

B. 3

C. 1

D. 2

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [0,2], [1,3], [2,4], [3,5], [4,6]

2. Step 2: Select intervals greedily and count removals

   Start with end = -Infinity, count = 0
   [0,2]: 0 >= -Infinity true, end=2
   [1,3]: 1 < 2 overlap, count=1
   [2,4]: 2 >= 2 true, end=4
   [3,5]: 3 < 4 overlap, count=2
   [4,6]: 4 >= 4 true, end=6

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Two intervals removed to avoid overlap [OK]

Hint: Sort by end, remove intervals starting before current end [OK]

Common Mistakes:

• Not sorting intervals before processing
• Counting intervals kept instead of removed
• Misunderstanding overlap conditions