LeetEye LeetEye
Medium Intervals ~5 min

Non-overlapping Intervals

intervals non-overlapping-intervals

Problem

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Examples

Example 1
Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Remove [1,3] to make the rest non-overlapping.
Example 2
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Example 3
Input: intervals = [[1,2],[2,3]]
Output: 0
Key Insight

Equivalent to: find maximum number of non-overlapping intervals (activity selection).

Activity selection: sort by end time. Greedily keep intervals that don't overlap with the last kept one. Removals = n - kept.

How to Approach This Problem

Pattern Recognition: When you see keywords like non-overlapping intervals intervals, think Intervals.

Step-by-Step Reasoning

1 Minimum removals = n - maximum non-overlapping. This is:
Answer: Activity selection problem
Classic greedy activity selection. Maximize intervals we can keep.
2 Sorting by end time:
Answer: Ensures we leave maximum room for future intervals
Picking interval that ends earliest leaves most time for remaining intervals.
3 When intervals overlap, we should remove:
Answer: The one that ends later
Interval ending later "blocks" more future intervals. Remove it.
4 After sorting by end, [a, b] overlaps with [c, d] if:
Answer: c < b
If next interval starts before current ends, they overlap. (Using strict < since [1,2],[2,3] don't overlap)
5 While iterating, we track:
Answer: Last interval's end (of kept intervals)
Compare next interval's start with last kept interval's end.

Solution

def eraseOverlapIntervals(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    
    # Sort by end time (activity selection)
    intervals.sort(key=lambda x: x[1])
    
    kept = 1
    end = intervals[0][1]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:  # No overlap
            kept += 1
            end = intervals[i][1]
    
    return len(intervals) - kept

Complexity Analysis

Time O(n log n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Intervals problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye