Non Overlapping Intervals Minimum Removal in DSA Javascript - Build from Scratch

Non Overlapping Intervals Minimum Removal

📖 Scenario: You are organizing a conference with multiple talks scheduled in different time intervals. Some talks overlap, and you want to remove the minimum number of talks so that no two talks overlap.

🎯 Goal: Build a program that finds the minimum number of intervals (talks) to remove so that the remaining intervals do not overlap.

📋 What You'll Learn

Create an array of intervals with exact start and end times

Add a variable to count removals

Implement the logic to find minimum removals to avoid overlaps

Print the final count of intervals to remove

💡 Why This Matters

🌍 Real World

Scheduling talks, meetings, or events without conflicts is a common real-world problem.

💼 Career

This problem is often asked in technical interviews to test understanding of sorting and greedy algorithms.

1

Create the intervals array

Create an array called intervals with these exact intervals: [1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11].

DSA Javascript

// Your code here

Hint

Use const intervals = [...] to create the array with the exact pairs.

2

Add a removal counter

Add a variable called removals and set it to 0 to count how many intervals we remove.

DSA Javascript

const intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]];
// Your code here

Hint

Use let removals = 0; to create the counter variable.

3

Implement the minimum removal logic

Sort the intervals array by the end time using intervals.sort((a, b) => a[1] - b[1]). Then, create a variable prevEnd set to the end time of the first interval. Use a for loop starting from index 1 to check each interval. If the current interval's start time is less than prevEnd, increment removals. Otherwise, update prevEnd to the current interval's end time.

DSA Javascript

const intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]];
let removals = 0;
// Your code here

Hint

Sort intervals by end time, then loop from the second interval. Compare start time with prevEnd to decide if removal is needed.

4

Print the minimum removals

Print the value of removals using console.log(removals).

DSA Javascript

const intervals = [[1, 3], [2, 4], [3, 5], [6, 7], [8, 10], [9, 11]];
let removals = 0;
intervals.sort((a, b) => a[1] - b[1]);
let prevEnd = intervals[0][1];
for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) {
        removals++;
    } else {
        prevEnd = intervals[i][1];
    }
}
// Your code here

Hint

Use console.log(removals) to show the final count.

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