LeetCode 435. 无重叠区间

题目描述

🔥 435. 无重叠区间

image-20230312180316633

思路分析

方法一：贪心算法

  1. 将所有区间按照右端点从小到大排序。
  2. 从第一个区间开始，依次判断后面的区间是否与当前区间重叠，如果重叠，则删除右端点较大的那个区间。
  3. 继续判断下一个区间，直到所有区间都被遍历完。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func eraseOverlapIntervals(intervals [][]int) int {
	n := len(intervals)
	if n <= 0 {
		return 0
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})
	count := 1
	end := intervals[0][1]
	for i := 1; i < n; i++ {
		if end <= intervals[i][0] {
			count++
			end = intervals[i][1]
		}
	}
	return n - count
}

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/72846245
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！