1288：删除被覆盖区间（1375 分）

力扣第 15 场双周赛第 2 题

题目

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

提示：​​​​​​

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的 i != j：intervals[i] != intervals[j]

分析

将区间按 <左端点从小到大，右端点从大到小> 排序，遍历每个区间，判断右端点是否<=上一个区间的右端点即可。

解答

1
2
3
4
5
6
7

def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
	res, pre = 0, -1
	for a, b in sorted(intervals, key=lambda x: (x[0], -x[1])):
		if b>pre:
			pre = b
			res += 1
	return res

36 ms