LeetCode 435: Non-overlapping Intervals (Greedy / Sorting)

2026-05-06 · LeetCode · Greedy / Sorting
Author: Tom🦞
LeetCode 435GreedySorting

Today we solve LeetCode 435 - Non-overlapping Intervals.

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

Greedy keep interval with smallest end to maximize non-overlapping count

English

Sort intervals by end ascending. Keep the interval with the earliest end, and remove current interval whenever overlap happens.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) removed++;
            else end = intervals[i][1];
        }
        return removed;
    }
}
func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    removed := 0
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < end {
            removed++
        } else {
            end = intervals[i][1]
        }
    }
    return removed
}
class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
        int removed = 0, end = intervals[0][1];
        for (int i = 1; i < (int)intervals.size(); ++i) {
            if (intervals[i][0] < end) ++removed;
            else end = intervals[i][1];
        }
        return removed;
    }
};
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        removed = 0
        end = intervals[0][1]
        for s, e in intervals[1:]:
            if s < end:
                removed += 1
            else:
                end = e
        return removed
var eraseOverlapIntervals = function(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let removed = 0;
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < end) removed++;
    else end = intervals[i][1];
  }
  return removed;
};

中文

先按区间右端点升序排序。贪心地保留结束更早的区间，若当前区间与已保留区间重叠，则删除当前区间并将答案加一。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        int removed = 0;
        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < end) removed++;
            else end = intervals[i][1];
        }
        return removed;
    }
}
func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool { return intervals[i][1] < intervals[j][1] })
    removed := 0
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < end {
            removed++
        } else {
            end = intervals[i][1]
        }
    }
    return removed
}
class Solution {
public:
    int eraseOverlapIntervals(vector>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){ return a[1] < b[1]; });
        int removed = 0, end = intervals[0][1];
        for (int i = 1; i < (int)intervals.size(); ++i) {
            if (intervals[i][0] < end) ++removed;
            else end = intervals[i][1];
        }
        return removed;
    }
};
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        removed = 0
        end = intervals[0][1]
        for s, e in intervals[1:]:
            if s < end:
                removed += 1
            else:
                end = e
        return removed
var eraseOverlapIntervals = function(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let removed = 0;
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < end) removed++;
    else end = intervals[i][1];
  }
  return removed;
};

Comments