Non Overlapping Intervals Minimum Removal in DSA Python

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] -> null
Goal: Remove minimum intervals so none overlap.

Dry Run Walkthrough

Input: intervals: [[1,3], [2,4], [3,5]]

Goal: Remove the fewest intervals so that remaining intervals do not overlap

Step 1: Sort intervals by end time

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

Why: Sorting by end time helps pick intervals that finish earliest first

Step 2: Keep first interval [1,3], set end = 3

[1,3] ↑ -> [2,4] -> [3,5]

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

Step 3: Check next interval [2,4], it starts before end=3, so it overlaps; remove it

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

Why: Overlap means we must remove this interval to avoid clash

Step 4: Check next interval [3,5], it starts at end=3, no overlap; keep it and update end=5

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

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

Result:

[1,3] -> [3,5] -> null
Minimum removals = 1

Annotated Code

DSA Python

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        # Sort intervals by their end time
        intervals.sort(key=lambda x: x[1])
        count = 0
        end = intervals[0][1]
        for i in range(1, len(intervals)):
            # If current interval starts before end, it overlaps
            if intervals[i][0] < end:
                count += 1  # Remove this interval
            else:
                end = intervals[i][1]  # Update end to current interval's end
        return count

# Driver code
intervals = [[1,3], [2,4], [3,5]]
sol = Solution()
print(sol.eraseOverlapIntervals(intervals))

intervals.sort(key=lambda x: x[1])

Sort intervals by their end time to pick earliest finishing intervals first

end = intervals[0][1]

Initialize end pointer to end of first interval

if intervals[i][0] < end:

Check if current interval overlaps with last kept interval

count += 1

Increment removal count for overlapping interval

else: end = intervals[i][1]

Update end pointer when interval does not overlap

Output

1

Complexity Analysis

Time: O(n log n) because we sort the intervals and then scan them once

Space: O(1) because sorting is in-place and only a few variables are used

vs Alternative: Naive approach checks all pairs for overlap leading to O(n^2) time, this greedy method is much faster

Edge Cases

empty intervals list

returns 0 because no intervals to remove

DSA Python

if not intervals:
    return 0

all intervals non-overlapping

returns 0 because no removals needed

DSA Python

if intervals[i][0] < end:

all intervals overlapping

removes all but one interval

DSA Python

count += 1

When to Use This Pattern

When asked to remove minimum intervals to avoid overlaps, use a greedy approach by sorting intervals by end time and removing overlapping ones.

Common Mistakes

Mistake: Sorting intervals by start time instead of end time
Fix: Sort intervals by their end time to ensure earliest finishing intervals are chosen first

Mistake: Not updating the end pointer after keeping an interval
Fix: Update end to current interval's end when interval does not overlap

Summary

Removes the fewest intervals so that no intervals overlap.

Use when you want to schedule intervals without clashes by removing minimum intervals.

Always pick intervals that finish earliest to leave room for others.

Practice

1. What is the main goal of the Non Overlapping Intervals Minimum Removal problem?

easy

A. To find the minimum number of intervals to remove so that the rest 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 the fewest intervals so that no two intervals overlap.

2. Step 2: Differentiate from related problems

   Unlike merging intervals or counting overlaps, here we minimize removals to avoid overlaps.

3. Final Answer:

   To find the minimum number of intervals to remove so that the rest do not overlap -> Option A

4. Quick Check:

   Minimum removals = non-overlapping intervals [OK]

Hint: Focus on removing intervals to avoid overlaps, not merging [OK]

Common Mistakes:

• Confusing with merging intervals problem
• Trying to maximize overlaps instead of minimizing removals
• Sorting intervals incorrectly

2. Which of the following Python code snippets correctly sorts a list of intervals by their end time?

easy

A. intervals.sort(key=lambda x: x[0])

B. intervals.sort(reverse=True)

C. intervals.sort(key=lambda x: x[1])

D. intervals.sort(key=lambda x: x[1], reverse=True)

Solution

1. Step 1: Identify sorting by end time

   Sorting by end time means using the second element of each interval, which is index 1.

2. Step 2: Check the correct syntax

   Using intervals.sort(key=lambda x: x[1]) sorts intervals ascending by end time.

3. Final Answer:

   intervals.sort(key=lambda x: x[1]) -> Option C

4. Quick Check:

   Sort by end time = key=lambda x: x[1] [OK]

Hint: Sort intervals by end time using key=lambda x: x[1] [OK]

Common Mistakes:

• Sorting by start time instead of end time
• Using reverse=True when not needed
• Incorrect lambda syntax

3. What is the output of the following code?

intervals = [[1,3],[2,4],[3,5]]
intervals.sort(key=lambda x: x[1])
count = 0
end = float('-inf')
for interval in intervals:
    if interval[0] >= end:
        end = interval[1]
    else:
        count += 1
print(count)

medium

A. 2

B. 1

C. 0

D. 3

Solution

1. Step 1: Sort intervals by end time

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

2. Step 2: Iterate and count overlaps

   Start with end = -inf
   Interval [1,3]: 1 >= -inf true, update end=3
   Interval [2,4]: 2 >= 3 false, count=1
   Interval [3,5]: 3 >= 3 true, update end=5

3. Final Answer:

   1 -> Option B

4. Quick Check:

   One interval removed to avoid overlap [OK]

Hint: Count intervals that start before current end to find removals [OK]

Common Mistakes:

• Not updating end correctly
• Counting non-overlapping intervals instead of removals
• Sorting by start time instead of end time

4. Find the error in this code snippet that tries to solve the minimum removal of overlapping intervals:

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[0])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

medium

A. The function should return intervals, not count

B. Using float('-inf') for end causes errors

C. The count variable should be initialized to 1

D. Sorting by start time instead of end time causes incorrect results

Solution

1. Step 1: Check sorting key

   The code sorts intervals by start time, but to minimize removals, sorting by end time is needed.

2. Step 2: Understand impact of sorting

   Sorting by start time can cause wrong overlap checks and incorrect count of removals.

3. Final Answer:

   Sorting by start time instead of end time causes incorrect results -> Option D

4. Quick Check:

   Sort by end time to minimize removals [OK]

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

Common Mistakes:

• Sorting by start time
• Incorrect initialization of end
• Returning wrong value

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. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: [[1,2],[2,3],[1,3],[3,4]]

2. Step 2: Select intervals greedily and count removals

   Start end = -inf
   [1,2]: 1 >= -inf true, end=2
   [2,3]: 2 >= 2 true, end=3
   [1,3]: 1 >= 3 false, count=1 (remove this)
   [3,4]: 3 >= 3 true, end=4

3. Final Answer:

   1 -> Option A

4. Quick Check:

   One interval removed to avoid overlap [OK]

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

Common Mistakes:

• Not sorting by end time
• Counting non-overlapping intervals instead of removals
• Removing wrong intervals