Non Overlapping Intervals Minimum Removal in DSA Typescript

Mental Model

We want to remove the fewest intervals so that no intervals overlap. We do this by always keeping intervals that end 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] -> [6,7]
Goal: Remove minimum intervals so none overlap.

Dry Run Walkthrough

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

Goal: Remove the fewest intervals so that remaining intervals do not overlap.

Step 1: Sort intervals by end time

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

Why: Sorting by end time helps pick intervals that finish earliest to maximize non-overlapping intervals.

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

[1,3] ↑ end=3 -> [2,4] -> [3,5] -> [6,7]

Why: Start with earliest finishing interval to compare others against.

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

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

Why: Interval [2,4] overlaps with [1,3], so remove it to avoid clash.

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

[1,3] -> [3,5] ↑ end=5 -> [6,7]

Why: No overlap, so keep and update end to 5.

Step 5: Check [6,7]: start 6 >= end 5 -> keep it, update end=7

[1,3] -> [3,5] -> [6,7] ↑ end=7

Why: No overlap, keep it.

Result:

[1,3] -> [3,5] -> [6,7]
Minimum removals = 1

Annotated Code

DSA Typescript

class Interval {
  start: number;
  end: number;
  constructor(start: number, end: number) {
    this.start = start;
    this.end = end;
  }
}

function eraseOverlapIntervals(intervals: Interval[]): number {
  if (intervals.length === 0) return 0;

  // Sort intervals by their end time
  intervals.sort((a, b) => a.end - b.end);

  let count = 0; // count of removals
  let end = intervals[0].end; // end time of last kept interval

  for (let i = 1; i < intervals.length; i++) {
    // If current interval starts before end, it overlaps
    if (intervals[i].start < end) {
      count++; // remove this interval
    } else {
      end = intervals[i].end; // update end to current interval's end
    }
  }

  return count;
}

// Driver code
const intervals = [new Interval(1,3), new Interval(2,4), new Interval(3,5), new Interval(6,7)];
const removals = eraseOverlapIntervals(intervals);
console.log(`Minimum removals = ${removals}`);

intervals.sort((a, b) => a.end - b.end);

Sort intervals by earliest end time to maximize non-overlapping intervals.

let end = intervals[0].end;

Initialize end to the end time of the first interval kept.

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

If current interval overlaps, increment removal count; else 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 do a single pass through them.

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

vs Alternative: A naive approach checking all pairs for overlap would be O(n^2), so sorting and greedy selection is much faster.

Edge Cases

empty intervals list

returns 0 removals since no intervals exist

DSA Typescript

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

all intervals non-overlapping

returns 0 removals because no overlaps

DSA Typescript

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

all intervals overlapping

removes all but one interval

DSA Typescript

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 intervals that finish earliest.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time.
Fix: Sort intervals by their end time to ensure earliest finishing intervals are chosen first.

Mistake: Not updating the end pointer after keeping an interval.
Fix: Update end to the current interval's end when it does not overlap.

Summary

Removes the fewest intervals so that no intervals overlap.

Use when you need to schedule intervals without conflicts by removing minimal intervals.

Always pick intervals that end earliest to leave room for others.

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