Non Overlapping Intervals Minimum Removal in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of minimum removals for overlapping intervals

What is the output of the following JavaScript code that calculates the minimum number of intervals to remove to avoid overlaps?

DSA Javascript

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[1] - b[1]);
  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;
}

const intervals = [[1,3],[2,4],[3,5],[6,7]];
console.log(eraseOverlapIntervals(intervals));

A 1

B 2

C 3

D 0

💡 Hint

Sort intervals by their end time and count overlaps.

The code sorts intervals by their end time and counts how many intervals overlap with the previous chosen interval. Only one interval needs removal to avoid overlaps.

🧠 Conceptual

intermediate

Key idea behind minimum removals in intervals

Which of the following best describes the key idea to find the minimum number of intervals to remove to avoid overlaps?

A Sort intervals by start time and remove intervals with the longest duration first.

B Sort intervals by start time and remove intervals that start earliest first.

C Sort intervals by length and remove the shortest intervals first.

D Sort intervals by end time and greedily keep intervals that finish earliest to maximize non-overlapping intervals.

💡 Hint

Think about maximizing the number of intervals you keep without overlap.

Sorting by end time and greedily choosing intervals that finish earliest allows keeping the maximum number of non-overlapping intervals, minimizing removals.

🔧 Debug

advanced

Identify the error in interval removal code

What error does the following code produce when run with intervals [[1,5],[2,3],[3,4]]? 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; } console.log(eraseOverlapIntervals([[1,5],[2,3],[3,4]]));

A Throws TypeError

B Outputs 2

C Outputs 0

D Outputs 1

💡 Hint

Check how sorting by start time affects overlap counting.

Sorting by start time instead of end time causes the algorithm to count more removals than necessary. The correct approach is to sort by end time.

❓ Predict Output

advanced

Output after removing minimum overlapping intervals

What is the output of the following code that returns the intervals after removing the minimum number of overlapping intervals?

DSA Javascript

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

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

A [[1,2],[1,3],[3,4]]

B [[1,3],[3,4]]

C [[1,2],[2,3],[3,4]]

D [[2,3],[3,4]]

💡 Hint

Check which intervals are kept after sorting by end time and skipping overlaps.

The code keeps intervals that start after or at the end of the last chosen interval, resulting in the non-overlapping intervals [[1,2],[2,3],[3,4]].

🧠 Conceptual

expert

Why does sorting by end time minimize removals in intervals?

Why does sorting intervals by their end time lead to the minimum number of removals to avoid overlaps?

A Because intervals with earlier end times leave more room for subsequent intervals, maximizing the count of non-overlapping intervals.

B Because sorting by length ensures the smallest intervals are kept, reducing overlaps.

C Because intervals with earlier start times always overlap less with others.

D Because sorting by start time allows removing intervals that start earliest, minimizing removals.

💡 Hint

Think about how choosing intervals that finish earliest affects the rest.

Choosing intervals that end earliest leaves maximum space for the rest, allowing more intervals to fit without overlap, thus minimizing 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 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