Non Overlapping Intervals Minimum Removal in DSA Javascript

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] -> [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 no two intervals overlap

Step 1: Sort intervals by end time

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

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] ↑ -> [2,4] -> [3,5] -> [6,7]

Why: Start with earliest finishing interval to maximize space for others

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

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

Why: Overlap means we must remove one; remove current to keep earliest end

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

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

Why: No overlap, so we keep this interval and update end

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

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

Why: No overlap, keep interval

Result:

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

Annotated Code

DSA Javascript

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

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;

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

  let end = intervals[0].end;
  let count = 0; // count of intervals removed

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i].start < end) {
      // Overlap detected, remove this interval
      count++;
    } else {
      // No overlap, update end to current interval's end
      end = intervals[i].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 prioritize keeping intervals that finish first

let end = intervals[0].end;

Initialize end to the end of the first interval to compare with next intervals

if (intervals[i].start < end) {

Check if current interval overlaps with last kept interval

count++;

Increment removal count because of overlap

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

Update end to current interval's end when no overlap

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 plus greedy is much faster

Edge Cases

empty intervals list

returns 0 removals since no intervals exist

DSA Javascript

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

all intervals non-overlapping

returns 0 removals because no overlaps occur

DSA Javascript

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

all intervals overlapping

removes all but one interval, returns n-1

DSA Javascript

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 time 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 correctly apply the greedy strategy

Mistake: Removing the wrong interval when overlap occurs
Fix: Always keep the interval with the earliest end time and remove the overlapping one

Summary

Removes the minimum number of intervals so that no intervals overlap.

Use when you want to schedule intervals without clashes by removing as few as possible.

The key is to sort by end time and greedily keep intervals that finish earliest.

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 sort intervals by their start time

D. To merge all overlapping intervals into one

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 intervals mean no two intervals share any common points except possibly at the boundary.

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:

• Confusing removal with merging intervals
• Thinking the goal is to count overlaps
• Assuming intervals must be sorted only

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

easy

A. intervals.sort((a, b) => b[0] - a[0]);

B. intervals.sort((a, b) => a[0] - b[0]);

C. intervals.sort((a, b) => b[1] - a[1]);

D. intervals.sort((a, b) => a[1] - b[1]);

Solution

1. Step 1: Identify sorting by end time

   Sorting by end time means comparing the second element of each interval, which is a[1] and b[1].

2. Step 2: Check the sorting order

   We want ascending order, so subtract a[1] - b[1] to sort from smallest to largest end time.

3. Final Answer:

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

4. Quick Check:

   Sort by end time ascending = intervals.sort((a, b) => a[1] - 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 sorting

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

const intervals = [[1,3],[2,4],[3,5]];
intervals.sort((a,b) => a[1] - b[1]);
let count = 0;
let end = -Infinity;
for (const [start, finish] of intervals) {
  if (start >= end) {
    end = finish;
  } else {
    count++;
  }
}
console.log(count);

medium

A. 3

B. 1

C. 0

D. 2

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [[1,3],[2,4],[3,5]] (already sorted by end time 3,4,5).

2. Step 2: Iterate and count removals

   Start with end = -Infinity.
   Interval [1,3]: start 1 >= -Infinity, update end=3, count=0.
   Interval [2,4]: start 2 < end 3, overlap, count=1.
   Interval [3,5]: start 3 >= end 3, update end=5, count=1.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   One interval removed to avoid overlap [OK]

Hint: Count overlaps after sorting by end time [OK]

Common Mistakes:

• Not updating end after choosing interval
• Counting non-overlapping intervals as removals
• Incorrectly sorting intervals

4. Find the bug in this JavaScript code for minimum interval removal:

function eraseOverlapIntervals(intervals) {
  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. Sorting by start time instead of end time causes incorrect removal count

B. The loop should start from i = 0, not 1

C. The variable 'count' should be initialized to 1

D. The 'end' variable should be updated inside the if condition

Solution

1. Step 1: Check sorting criteria

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

2. Step 2: Understand impact of sorting

   Sorting by start time can cause counting more removals than necessary because it doesn't prioritize earliest finishing intervals.

3. Final Answer:

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

4. Quick Check:

   Sort by end time for correct removal count [OK]

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

Common Mistakes:

• Sorting by start time instead of end time
• Not updating 'end' correctly after removal
• Starting loop from wrong index

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

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

2. Step 2: Select intervals greedily and count removals

   Choose [1,2], end=2.
   [2,3] start 2 >= 2, choose, end=3.
   [1,3] start 1 < 3, overlap, remove count=1.
   [3,4] start 3 >= 3, choose, end=4.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   One interval removed to avoid overlap [OK]

Hint: Sort by end time, pick intervals greedily, count overlaps [OK]

Common Mistakes:

• Not sorting intervals before processing
• Counting non-overlapping intervals as removals
• Ignoring intervals with same end time