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.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4

Solution

Approach: Greedy (Sort by End Time)

The key insight is to keep intervals with earliest end times. This leaves maximum room for future intervals.

Implementation

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0

        # Sort by end time
        intervals.sort(key=lambda x: x[1])

        count = 0
        prev_end = intervals[0][1]

        for i in range(1, len(intervals)):
            # If current interval starts before previous ends, overlap
            if intervals[i][0] < prev_end:
                count += 1
            else:
                # No overlap, update end time
                prev_end = intervals[i][1]

        return count

Approach 2: Sort by Start Time

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        count = 0
        prev_end = intervals[0][1]

        for i in range(1, len(intervals)):
            if intervals[i][0] < prev_end:
                # Overlap - remove the one with later end time
                count += 1
                prev_end = min(prev_end, intervals[i][1])
            else:
                prev_end = intervals[i][1]

        return count

Complexity Analysis

Time Complexity: O(n log n), where n is the number of intervals. Sorting dominates.
Space Complexity: O(1), not counting space for sorting.

Key Insights

Activity Selection: This is a variant of the classic activity selection problem.
Greedy Choice: Always keep the interval with the earliest end time. This maximizes room for future intervals.
Sort by End: Sorting by end time is more intuitive for this greedy approach.
Overlap Detection: After sorting by end time, an interval overlaps with previous if start < prev_end.
Count Removals: We count how many intervals we skip (remove) due to overlaps.
Why Greedy Works: Choosing intervals with earliest end times is always optimal - if there’s a solution with a different choice, we can swap it for the earlier-ending interval.