LeetCode1288. 删除被覆盖区间

Yuyy

发布于 2022-06-28 20:22:35

1550

发布于 2022-06-28 20:22:35

文章被收录于专栏：yuyy.info技术专栏yuyy.info技术专栏

本文最后更新于 484 天前，其中的信息可能已经有所发展或是发生改变。

一、思路

通过画图分析出区间覆盖的条件区间问题一般通过排序，才能更好的处理

二、问题

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

只有当 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]

三、代码

public int removeCoveredIntervals(int[][] intervals) {
            Arrays.sort(intervals, (o1, o2) -> {
                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
            });
            int count = 0;
            int preEnd = 0;
            for (int i = 0; i < intervals.length; i++) {
                if (intervals[i][1] > preEnd) {
                    count++;
                    preEnd = intervals[i][1];
                }
            }
            return count;
        }

Post Views: 214

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2021-2-28 1，如有侵权请联系 cloudcommunity@tencent.com 删除

intervals