Non-overlapping Intervals: Earliest End Greedy Pattern

Learning Outcome

After this lesson, you should be able to sort by ending time and keep the maximum number of compatible intervals.

Problem Statement

Given intervals, return the minimum number of intervals to remove so the rest do not overlap.

Brute Force Approach

Try every subset of intervals and choose the largest non-overlapping subset. This is exponential.

Optimized Approach

Sort intervals by end time. Keep an interval when its start is at or after the last kept end.

Exact Pseudocode

sort intervals by end
kept = 0
lastEnd = -infinity
for interval in intervals:
  if interval.start >= lastEnd:
    kept += 1
    lastEnd = interval.end
return intervals.length - kept
  

Reference Code

class Solution:
    def eraseOverlapIntervals(self, intervals):
        intervals.sort(key=lambda x: x[1])
        kept = 0
        last_end = float("-inf")

        for start, end in intervals:
            if start >= last_end:
                kept += 1
                last_end = end

        return len(intervals) - kept
  

Sample Dry Run

Complexity

Edge Cases

• Touching intervals like [1,2] and [2,3] do not overlap.
• An empty list needs 0 removals.
• Sort by end time, not by interval length.

Interview Checklist

• Keep the interval that ends earliest.
• Count kept intervals, then subtract from total.
• Use start >= lastEnd for non-overlap.

FAQs