435.Non-overlapping_Intervals(Medium).md

435. Non-overlapping Intervals (Medium)

Date and Time: Sep 6, 2024, 12:48 (EST)

Link: https://leetcode.com/problems/non-overlapping-intervals/

Question:

Given an array of intervals intervals where intervals[i] = [start_i, end_i], 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 <= start_i < end_i <= 5 * 10^4

Walk-through:

1. Sort the intervals first.

2. We use prevEnd to compare if a new intervals[i] needs to be removed or not. If start[i] >= prevEnd, it means there is no overlapping between the previous interval and the current one, and we just need to update prevEnd = end (intervals[i] comes later). Otherwise, we increment res and find the minimum prevEnd by prevEnd = min(prevEnd, end), because we want to shorten the interval to prevent having more overlapping intervals.

The whole point is that, we want to merge the interval after we compare, so we just extend the end when we have no overlapping, otherwise, we should shorten the interval because we want to find the minimum number of intervals we need to remove.

Python Solution:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res = 0
        prevEnd = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= prevEnd:
                prevEnd = end
            else:
                res += 1
                prevEnd = min(end, prevEnd)
        return res

Time Complexity: $O(nlog\ n)$, sort takes $O(nlog\ n)$ and we loop over all intervals take $O(n)$.
Space Complexity: $O(1)$