LeetCode 0435. Non-overlapping Intervals Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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

We first sort the intervals in ascending order by their right boundary. We use a variable pre to record the right boundary of the previous interval and a variable ans to record the number of intervals that need to be removed. Initially, ans = 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 pre, it means that this interval does not need to be removed. We directly update pre to the right boundary of the current interval and decrement ans by one;
• Otherwise, it means that this interval needs to be removed, and we do not need to update pre and ans.

Finally, we return ans.

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

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)