Skip to content

435. Non-overlapping Intervals

Description

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

Solutions

Solution 1: Sorting + Greedy

Thinking

Removing the fewest intervals so the rest are disjoint is the same as keeping the largest set of non-overlapping intervals. Subset search is too large.

Sort by right endpoint and keep an interval when it starts at or after the last kept end. The earliest finish leaves the most room, which is why we sort by the right end.

The answer starts at \(n\) and decreases once per kept interval: total minus the size of a maximum compatible set.

We first sort the intervals in ascending order by their right boundary. We use a variable \(\textit{pre}\) to record the right boundary of the previous interval and a variable \(\textit{ans}\) to record the number of intervals that need to be removed. Initially, \(\textit{ans} = \textit{intervals.length}\).

Then we iterate through the intervals. For each interval:

  • If the left boundary of the current interval is greater than or equal to \(\textit{pre}\), it means that this interval does not need to be removed. We directly update \(\textit{pre}\) to the right boundary of the current interval and decrement \(\textit{ans}\) by one;
  • Otherwise, it means that this interval needs to be removed, and we do not need to update \(\textit{pre}\) and \(\textit{ans}\).

Finally, we return \(\textit{ans}\).

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\), where \(n\) is the number of intervals.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        ans = len(intervals)
        pre = -inf
        for l, r in intervals:
            if pre <= l:
                ans -= 1
                pre = r
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int ans = intervals.length;
        int pre = Integer.MIN_VALUE;
        for (var e : intervals) {
            int l = e[0], r = e[1];
            if (pre <= l) {
                --ans;
                pre = r;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        ranges::sort(intervals, [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int ans = intervals.size();
        int pre = INT_MIN;
        for (const auto& e : intervals) {
            int l = e[0], r = e[1];
            if (pre <= l) {
                --ans;
                pre = r;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    ans := len(intervals)
    pre := math.MinInt32
    for _, e := range intervals {
        l, r := e[0], e[1]
        if pre <= l {
            ans--
            pre = r
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function eraseOverlapIntervals(intervals: number[][]): number {
    intervals.sort((a, b) => a[1] - b[1]);
    let [ans, pre] = [intervals.length, -Infinity];
    for (const [l, r] of intervals) {
        if (pre <= l) {
            --ans;
            pre = r;
        }
    }
    return ans;
}

Comments