Non Overlapping Intervals Minimum Removal in DSA Javascript - Time & Space Complexity

Time Complexity: Non Overlapping Intervals Minimum Removal

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to remove overlapping intervals grows as the number of intervals increases.

How does the code handle checking and removing overlaps when there are more intervals?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function eraseOverlapIntervals(intervals) {
  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;
}
    

This code sorts intervals by their end time, then counts how many intervals must be removed to avoid overlaps.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the intervals array.
• How many times: Sorting takes multiple comparisons depending on the number of intervals (n).
• Secondary operation: One loop through all intervals to check overlaps.
• How many times: Exactly once for each interval (n times).

How Execution Grows With Input

Sorting grows faster than just looping. As intervals increase, sorting takes more time compared to the simple loop.

Input Size (n)	Approx. Operations
10	About 10 * log(10) + 10 = 43 operations
100	About 100 * log(100) + 100 = 700 operations
1000	About 1000 * log(1000) + 1000 = 10,000 operations

Pattern observation: The sorting step dominates and grows a bit faster than just doubling the input size.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of intervals because of sorting, but the checking loop adds only a simple step per interval.

Common Mistake

[X] Wrong: "The loop checking overlaps is the slowest part, so the complexity is O(n)."

[OK] Correct: Sorting the intervals first takes more time than the loop, so the overall time depends mostly on sorting, not just the loop.

Interview Connect

Understanding how sorting affects time helps you explain your solution clearly and shows you know where the main cost lies in interval problems.

Self-Check

"What if the intervals were already sorted by their start time? How would the time complexity change?"

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