mediumIntervals

Non-overlapping Intervals

Remove as few intervals as possible so the rest do not overlap. Here, intervals that only share an endpoint are compatible.

LeetCode ↗

Work through the cases

3 examples

Input notation

One start end pair per line, with start < end.

Expected result

The minimum number of removals.

Case 1

Input

1 2
2 3
1 3

Expected output

Case 2

Input

1 2
3 4

Expected output

Case 3

Input

1 2
1 2
1 2

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

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 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.

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;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.