LeetCode 435: Non-overlapping Intervals

Problem Description

LeetCode Problem 435

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.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are 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 <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

Difficulty: Medium

Tags: array, dynamic programming, greedy, sorting

Rating: 97.38%

Solution

Here’s my Python solution to this problem:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x:x[1])
        prev_end = intervals[0][1]

        res = 0
        for s, e in intervals[1:]:
            if s < prev_end:
                res += 1
            else:
                prev_end = e
        
        return res

Example Walkthrough

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

After sorting by end time: [[1, 2], [1, 3], [2, 3], [3, 4]]

• We start with the first interval [1, 2] and set prev_end to 2.
• Next, we consider the interval [1, 3]. Since the start time 1 is less than prev_end, we increment the result by 1.
• We continue this process for the remaining intervals and return the result.

The final result is 1, which is the minimum number of intervals to remove to make the rest of the intervals non-overlapping.

Given intervals: [[1,2],[1,2],[1,2]]

After sorting by end time: [[1, 2], [1, 2], [1, 2]]

• We start with the first interval [1, 2] and set prev_end to 2.
• Next, we consider the interval [1, 2]. Since the start time 1 is less than prev_end, we increment the result by 1.
• We continue this process for the remaining intervals and return the result.

The final result is 2, which is the minimum number of intervals to remove to make the rest of the intervals non-overlapping.

Complexity Analysis

The solution has the following complexity characteristics:

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Note: This is an automated analysis and may not capture all edge cases or specific algorithmic optimizations.