> LeetCode1288. 删除被覆盖区间 - Yuyy
Yuyy
Yuyy
LeetCode1288. 删除被覆盖区间

一、思路

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

二、问题

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

只有当 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 != jintervals[i] != intervals[j]
Related Topics
  • 贪心算法
  • 排序
  • Line Sweep
  • \n

  • 👍 39
  • 👎 0
  • 三、代码

    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;
            }
    

    发表评论

    textsms
    account_circle
    email

    Yuyy

    LeetCode1288. 删除被覆盖区间
    一、思路 通过画图分析出区间覆盖的条件 区间问题一般通过排序,才能更好的处理 二、问题 给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。 只有当 c
    扫描二维码继续阅读
    2021-02-28
    友情链接
    标签
    归档
    近期文章