Java实现 LeetCode 757 设置交集大小至少为2(排序+滑动窗口)
2023-09-14 08:58:02 时间
757. 设置交集大小至少为2
一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b。
给你一组整数区间intervals,请找到一个最小的集合 S,使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
输出这个最小集合S的大小。
示例 1:
输入: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
输出: 3
解释:
考虑集合 S = {2, 3, 4}. S与intervals中的四个区间都有至少2个相交的元素。
且这是S最小的情况,故我们输出3。
示例 2:
输入: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
输出: 5
解释:
最小的集合S = {1, 2, 3, 4, 5}.
注意:
intervals 的长度范围为[1, 3000]。
intervals[i] 长度为 2,分别代表左、右边界。
intervals[i][j] 的值是 [0, 10^8]范围内的整数。
class Solution {
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1]==o2[1]){
return o2[0]-o1[0];
}
return o1[1]-o2[1];
}
});
int[] rec = {-1,-1};
int res=0;
for(int[] is : intervals){
if(is[0]<=rec[0]){
continue;
}else if(is[0] <= rec[1]){
res++;
rec[0] = rec[1];
}else{
rec[0] = is[1]-1;
res+=2;
}
rec[1] = is[1];
}
return res;
}
}
相关文章
- java 字符串转集合_字符串转化为 List 集合
- 成为java架构师需要具备那些技能?
- java怎么输出保留两位小数_剖析Java输出怎么保留两位小数「建议收藏」
- java怎么写函数_java构造函数怎么写
- java冒泡排序经典代码_Java 8大经典排序算法(含源代码),必须收藏!
- java 生成xml dom4j_Java生成xml——DOM4J生成
- 【说站】java Clock如何访问时间
- Tomcat在Java开发中的使用笔记
- Java关键字 transient
- java date当前时间_JAVA中获取当前系统时间
- Java基于springboot大学生宿舍寝室考勤人脸识别管理系统
- 最新的极光推送服务器端代码(java服务器后台向手机端自定义推送消息)详解编程语言
- java评选最佳编程语言详解编程语言
- MySQL与Java的无缝互联(java与mysql连接)
- Java高效操作MySQL数据库(java写入mysql)
- 数据处理解决Java程序中Redis过期数据的问题(redisjava过期)
- 挑战未来:学习Linux与Java(学linux还是java)
- 策略设计基于Redis的java过期策略(redisjava过期)
- 时间Redis Java中设置过期时间的简单方法(redisjava过期)
- Linux下运行Java:一步步踏上学习之路(linux下运行java)
- Java程序调用Linux系统命令实现更多功能(java调用linux命令)
- 语句Java自动生成Oracle数据库查询语句(java生成oracle)
- 构建基于Java和Oracle的强大技术栈(java架构oracle)
- Java存入Oracle数据库实现快速高效的数据存储(java存入oracle)
- 数据库以Java运行环境构建基于Oracle的数据库(java创建oracle)
- Java如何帮助掌握Oracle(java了解oracle)
- JAVA/JSP学习系列之二
- java判断远程服务器上的文件是否存在的方法
- java中Scanner类的简单用法分享
- java批量采集豌豆荚网站Android应用图标和包名