Non Overlapping Intervals Minimum Removal in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort intervals by their end time.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Astart - end

Ba.end - b.end

C0

Dend - start

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start time instead of end time.

Using incorrect subtraction order.

Returning 0 which means no sorting.

Sorting intervals by their end time helps to greedily select intervals that finish earliest, minimizing overlaps.

2fill in blank

medium

Complete the code to check if the current interval overlaps with the last selected interval.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A[last]

B[i + 1]

C[i]

D[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with the current interval itself.

Using i + 1 which is the next interval.

Using 0 which is the first interval always.

We compare the start of the current interval with the end of the last selected interval to detect overlap.

3fill in blank

hard

Fix the error in updating the end time of the last selected interval to the minimum end time.

DSA Javascript

intervals[1].end = Math.min(intervals[i].end, intervals[2].end);

Drag options to blanks, or click blank then click option'

A[last]

B[i]

C[i + 1]

D[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Updating the current interval instead of the last selected.

Using i + 1 which is out of range or next interval.

Using 0 which is the first interval always.

We update the end time of the last selected interval to the minimum of its current end and the current interval's end to keep intervals non-overlapping.

4fill in blank

hard

Fill both blanks to correctly count removals and update the last selected interval index.

DSA Javascript

if (intervals[i].start < intervals[1].end) {
  removals[2];
} else {
  last = i;
}

Drag options to blanks, or click blank then click option'

A[last]

B++removals

Cremovals++

D--removals

Attempts:

3 left

💡 Hint

Common Mistakes

Using post-increment removals++ which may cause subtle bugs.

Decreasing removals instead of increasing.

Using wrong index instead of last.

We check overlap with the last selected interval and increase removals count using prefix increment. If no overlap, update last to current index.

5fill in blank

hard

Fill all three blanks to complete the function that returns minimum removals for non-overlapping intervals.

DSA Javascript

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => [1]);
  let removals = 0;
  let last = 0;
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i].start < intervals[2].end) {
      removals[3];
      intervals[last].end = Math.min(intervals[i].end, intervals[last].end);
    } else {
      last = i;
    }
  }
  return removals;
}

Drag options to blanks, or click blank then click option'

Aa.end - b.end

B[last]

C++removals

D[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start instead of end.

Using wrong index for overlap check.

Using post-increment instead of prefix increment.

Sort by end time, check overlap with last selected interval, increment removals if overlap, update last interval end to minimum, else update last index.

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