LeetCode 435. 无重叠区间

Categories:

题目描述
思路分析
1. 解法一：按右端点贪心（推荐）
相似题目

题目描述

✅ 435. 无重叠区间

思路分析

解法一：按右端点贪心（推荐）

核心思路：

将区间按右端点升序排序。

选择右端点最小的区间，尽量给后续留空间。

若当前区间与已选区间重叠，则需要移除当前区间。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示区间数量。

空间复杂度：O(1)（不计排序开销）。

// 按右端点排序贪心
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int end = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] < end) {
                count++;
            } else {
                end = interval[1];
            }
        }

        return count;
    }
}

// 按右端点排序贪心
func eraseOverlapIntervals(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})

	count := 0
	end := -1 << 60
	for _, interval := range intervals {
		if interval[0] < end {
			count++
		} else {
			end = interval[1]
		}
	}

	return count
}

相似题目

题目	难度	考察点
452. 用最少数量的箭引爆气球	中等	贪心
56. 合并区间	中等	区间
57. 插入区间	中等	区间
986. 区间列表的交集	中等	区间
1094. 拼车	中等	区间
646. 最长数对链	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/72846245