无重叠区间问题
2023-02-18 16:36:42 时间
无重叠区间问题
作者:Grey
原文地址:
题目描述
思路
题目要求至少移除多少个线段可以保证线段不出现重叠区域,比如以下情况:
我们至少需要移走四条线段才能让剩余线段不重叠。移动后的线段如下图
我们可以反过来考虑,即求所有非重叠区域的个数,假设是M,线段数量假设是N,那么N-M
即为需要移除的线段数量。
主要流程如下,先把所有线段按结尾位置排序,结尾小的排前面,结尾大的排后面。
然后遍历每个线段,如果线段的开始位置超过了前一个线段的结尾位置,说明这两个线段是非重叠的,非重叠个数加1,遍历完毕,用所有线段个数减去非重叠个数,即为需要移除的线段个数。
完整代码
public class LeetCode_0435_NonOverlappingIntervals {
public static int eraseOverlapIntervals(int[][] intervals) {
if (null == intervals || intervals.length <= 1) {
return 0;
}
Interval[] arr = new Interval[intervals.length];
int i = 0;
for (int[] interval : intervals) {
arr[i++] = new Interval(interval[0], interval[1]);
}
Arrays.sort(arr, Comparator.comparingInt((Interval o) -> o.end));
// 非重叠区域个数
int notOverlap = 1;
int b = arr[0].end;
for (i = 1; i < arr.length; i++) {
if (arr[i].start >= b) {
notOverlap++;
b = arr[i].end;
}
}
return arr.length - notOverlap;
}
public static class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
}
更多
相关文章
- DBA 面对的几种 数据库“问题” 制造者 (Database killer)
- 做完这套面试题,你才敢说懂Excel
- 图解面试题:如何实现精细化运营?
- 美团在深圳成立机器人研究院;移动发布物联网操作系统;百度Apollo公布自动驾驶最新进展|每日大事件
- GCTA如何计算GWAS中SNP的遗传力
- 一道sql面试题
- 华为云副总裁薛浩:云原生视频服务,重塑体验,助力产业升级
- 4大华为云“安全镖局”秘密法宝揭秘
- 数据加密:你应该知道的数仓安全
- 带你了解数据库的“吸尘器”:VACUUM
- 基于深度学习的两种信源信道联合编码
- 6大创新技术及2亿美元投入计划,这个活动有点料
- MindSpore实践:对篮球运动员目标的检测
- IAP:物联网终端软件升级技术
- 终于知道为啥网页不让我复制粘贴了!
- 基于深度学习的端到端通信系统模型
- 开抢| 华为开发者大会2021(Cloud)早鸟票来了!
- 云原生数据库风起云涌,华为云GaussDB破浪前行
- 聊聊LiteOS中生成的Bin、HEX、ELF三种文件格式
- 实践解析丨Rust 内置 trait:PartialEq 和 Eq