给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
//"区间"定义
class Interval {
int start; //起点
int end; //终点
}
数据范围：区间组数 
，区间内 的值都满足 
要求：空间复杂度 )
，时间复杂度 )
进阶：空间复杂度 )
，时间复杂度
[编程题]合并区间
提醒一下 这个代码过不了一部分测试用例，针对[0,0][1,4]这样的测试用例，应该说区间是个连续值，进阶版里面按o(val)的下意识让我想到用布尔数组做，虽然过不了所有用例还是浅浅mark一下
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
int max = 0;
for (Interval i : intervals) {
max = i.end > max ? i.end : max;
}
boolean[] arr = new boolean[max + 1];
Arrays.fill(arr, false);
for (Interval i : intervals) {
Arrays.fill(arr, i.start, i.end, true);
}
// 重新构造区间
// 区间开闭信号
boolean flag = false;
Interval inv = new Interval(0, 0);
ArrayList<Interval> res = new ArrayList<Interval>();
for (int i = 0; i < max + 1; i++) {
if (!flag) {
// 等待一个区间开始信号
if (arr[i]) {
inv.start = i;
flag = true;
continue;
}
} else {
// 等待一个闭区间信号
if (!arr[i]) {
inv.end = i;
flag = false;
res.add(inv);
inv = new Interval(0, 0);
continue;
}
}
}
// 有一种情况是循环到了最后一位，区间还没关闭，得判断一下
if (flag) {
inv.end = max;
flag = false;
res.add(inv);
}
return res;
}
}
发表于 2025-04-28 14:35:16
回复(0)
最简单的做法就是排序
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
if(intervals.size()<=1)
return intervals;
intervals.sort((a,b)->a.start-b.start);
int start = intervals.get(0).start;
int end = intervals.get(0).end;
ArrayList<Interval> answer = new ArrayList<Interval>();
for(int i=1;i<intervals.size();i++){
if(intervals.get(i).start>=start&&intervals.get(i).start<=end){
end = Math.max(end,intervals.get(i).end);
}else{
answer.add(new Interval(start,end));
start = intervals.get(i).start;
end = intervals.get(i).end;
}
}
answer.add(new Interval(start,end));
return answer;
} 进阶版的时间和空间复杂度，让我猜测是不是应该这么写 /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
if (intervals.size() <= 1)
return intervals;
//找到最大的起始start位置，时间复杂度O(n)
int max = intervals.get(0).start;
for (int i = 1; i < intervals.size(); i++) {
if (intervals.get(i).start > max) {
max = intervals.get(i).start;
}
}
ArrayList<Interval> answer = new ArrayList<Interval>();
//生成0-max大小的区间，对应数字代表区间的长度
int[] length = new int[max + 1]; //空间复杂度O(val)
//时间复杂度O(n)
for (int i = 0; i < intervals.size(); i++) {
int len = intervals.get(i).end - intervals.get(i).start + 1; //记录区间长度
if (length[intervals.get(i).start] != 0) { //当前已经有区间
length[intervals.get(i).start] = Math.max(len, length[intervals.get(i).start]);
} else {
length[intervals.get(i).start] = len;
}
}
//添加区间
int start = -1;
int end = -2;
//时间复杂度O(val)
for (int i = 0; i < max+1; i++) {
if(end>=0&&i>end){ //找到一个完整的区间了
answer.add(new Interval(start,end));
start = -1;
end = -2;
}
if(length[i]!=0){ //当前有区间
if(start==-1){ //没有包含区间
start = i;
end = length[i]+i-1;
}else{
end = Math.max(end,length[i]+i-1); //合并区间
}
}
}
answer.add(new Interval(start, end));
return answer;
}
发表于 2025-02-10 19:48:52
回复(0)
public class Solution {
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
if (intervals.size() <= 1) return intervals;
Collections.sort(intervals, (a, b)-> {
return a.start <= b.start ? -1 : 1;
});
ArrayList<Interval> res = new ArrayList<Interval>();
res.add(intervals.get(0));
for (int i = 1; i < intervals.size(); i++) {
if (res.get(res.size() - 1).end >= intervals.get(i).start) {
res.get(res.size() - 1).end = Math.max(intervals.get(i).end,res.get(res.size() - 1).end);
} else res.add(intervals.get(i));
}
return res;
}
}
发表于 2024-10-13 20:36:25
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
ArrayList<Interval> list = new ArrayList();
if(intervals.size()==0)
return list;
int count = 0;
intervals.sort((a,b)-> a.start-b.start);
list.add(intervals.get(0));
for(int i = 1;i < intervals.size();i++){
Interval t1 = intervals.get(i);
Interval t2 = list.get(count);
if(t2.end>=t1.start){
int start = t1.start>t2.start?t2.start:t1.start;
int end = t1.end>t2.end?t1.end:t2.end;
list.remove(count);
Interval t3 = new Interval(start,end);
list.add(t3);
}else{
list.add(t1);
count++;
}
}
return list;
}
}
发表于 2024-08-26 14:28:32
回复(0)
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// 根据start进行从小到大排序, 将start end 2个影响因素降为1个
intervals.sort((a, b) -> a.start - b.start);
ArrayList<Interval> resList = new ArrayList<>();
// 数组为空, 或者长度为1直接返回
if (intervals.size() < 2) {
return intervals;
}
// 双指针左指针
Interval pre = intervals.get(0);
resList.add(pre);
for (int i = 1; i < intervals.size(); i++) {
// 双指针右指针
Interval curr = intervals.get(i);
// 有合二为一的情况。设置合并后的右区间
if (curr.start >= pre.start && curr.start <= pre.end) {
pre.end = curr.end >= pre.end ? curr.end : pre.end;
// 无合并情况, 直接添加, 并且左指针后移
} else {
resList.add(curr);
pre = curr;
}
}
return resList;
}
发表于 2024-06-29 23:32:04
回复(0)
看到大部分题解都是sort排序，然后遍历合并，我分享一种比较取巧的合并。
因为数值范围较小，所以先开 200001 的数组 lengthArray ，里面保存的是从改位置开始，共有几个数字，例如 [10, 20] 就可以转换为 lengthArray[10] = 11，标识从坐标 10 开始有 11 个数字（包括自身）。随后遍历 lengthArray，如果存在 length，则length--；如果 length变为 0，说明一个范围终止，则加入结果队列中。
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
// write code here
if (intervals.size() <= 1) {
return intervals;
}
int maxLength = 200001;
int[] lengthArray = new int[maxLength];
for (Interval interval : intervals) {
lengthArray[interval.start] = Math.max(interval.end - interval.start + 1, lengthArray[interval.start]);
}
int startPos = -1;
int length = -1;
ArrayList<Interval> resultList = new ArrayList<>();
for (int i = 0; i < maxLength; i++) {
if (length > 0) {
length--;
if (length == 0) {
resultList.add(new Interval(startPos, i - 1));
length = -1;
startPos = -1;
}
}
if (length > 0 && lengthArray[i] > 0) {
length = Math.max(length, lengthArray[i]);
} else if (length == -1 && lengthArray[i] > 0) {
startPos = i;
length = lengthArray[i];
}
}
return resultList;
}
发表于 2024-06-05 15:07:22
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
if (intervals.size() <= 1) {
return intervals;
}
Collections.sort(intervals, (a, b) -> a.start - b.start);
Interval pre = new Interval(intervals.get(0).start, intervals.get(0).end);
ArrayList<Interval> res = new ArrayList<>();
for (Interval interval : intervals) {
if (interval.start <= pre.end) {
pre.end = Math.max(interval.end, pre.end);
}else {
res.add(pre);
pre = interval;
}
}
res.add(pre);
return res;
}
}
发表于 2024-06-04 15:50:23
回复(0)
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
PriorityQueue<Interval> queue=new PriorityQueue<>(new Comparator<Interval>(){
@Override
public int compare(Interval i1 ,Interval i2){
if(i1.start==i2.start){
return i1.end-i2.end;
}else{
return i1.start-i2.start;
}
}
});
for(Interval i:intervals){
queue.add(i);
}
ArrayList<Interval> res=new ArrayList<>();
while(!queue.isEmpty()){
Interval interval=queue.poll();
while(!queue.isEmpty() && queue.peek().start<=interval.end){
interval.end=Math.max(interval.end ,queue.poll().end);
}
res.add(interval);
}
return res;
}
发表于 2024-06-02 14:01:18
回复(0)
先按start排个序，然后只需要比较当前元素end和后一个元素start\end的关系即可
分三种情况：
1、当前元素end<后一个元素start,无需做任何操作
2、当前元素end>=后一个元素start且当前end>=后一个end,删除后一位元素，并将遍历下标减1
3、当前元素end>=后一个元素start且当前end<后一个end,将当前元素end设置位后一个元素end,删除后一位元素，并将遍历下标减1
public class Solution {
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
for (int i = 0; i < intervals.size() - 1; i++) {
Interval cur = intervals.get(i);
Interval next = intervals.get(i + 1);
if (next.start <= cur.end) {
if (next.end <= cur.end) {
intervals.remove(i + 1);
i--;
} else {
cur.end = next.end;
intervals.remove(i + 1);
i--;
}
}
}
return intervals;
}
}
发表于 2024-05-11 19:57:22
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
if (intervals.isEmpty()) return new ArrayList<>();
intervals.sort((o1, o2) -> o1.start - o2.start);
Iterator<Interval> ite = intervals.iterator();
Interval prev = ite.next();
while (ite.hasNext()) {
Interval next = ite.next();
if (prev.end >= next.start) {
if (prev.end >= next.end) {
ite.remove();
} else {
prev.end = next.end;
ite.remove();
}
} else {
prev = next;
}
}
return intervals;
}
} 迭代器解法，感觉比别人的更好理解，利用了 Java 8 迭代器中 remove 的方法，同时储存prev和next，不用考虑循环的索引问题。
编辑于 2024-04-15 19:53:42
回复(0)
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals == null || intervals.size() < 2) {
return intervals;
}
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
ArrayList<Interval> newList = new ArrayList<>();
Interval prev = intervals.get(0);// 上一个需要合并的
int index = 1;
while (index < intervals.size()) {
Interval current = intervals.get(index);// 得到当前的节点，
//用当前节点和上一节点做对比
if (prev.end >= current.start) {
//重叠，需要合并,更新上一节点,否则不用更新，维持prev，继续向后遍历
if (prev.end < current.end) {
prev.end = current.end;
}
} else {
// 不重叠，那么添加上一节点
newList.add(prev);
prev = current;
}
index ++;
}
newList.add(prev);
return newList;
}
}
编辑于 2024-02-27 15:52:50
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
ArrayList<Interval> newIntervals = new ArrayList<>();
Collections.sort(intervals, (a, b) -> a.start - b.start);
int len = intervals.size();
for(int i = 0; i < intervals.size(); i++){
Interval node = new Interval(intervals.get(i).start, intervals.get(i).end);
while(i < len - 1){
i++;
if(intervals.get(i).start <= node.end && intervals.get(i).end > node.end){
node.end = intervals.get(i).end;
}else if(intervals.get(i).start > node.end){
i--;
break;
}
}
newIntervals.add(node);
}
return newIntervals;
}
} 为什么用时这么久
发表于 2024-01-16 14:35:18
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
// Interval类:https://wenku.baidu.com/view/48557165cf1755270722192e453610661fd95a5b.html?_wkts_=1698997239332&bdQuery=JavaInterval%E6%98%AF%E4%BB%80%E4%B9%88%E7%B1%BB&needWelcomeRecommand=1
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
ArrayList<Interval> res = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) return res;
// 排序
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
// 区间起始值不同
if (o1.start != o2.start) {
return o1.start - o2.start;
// 区间起始值相同，比较区间末尾值
} else {
return o1.end - o2.end;
}
}
});
// 初始化结果集，将intervals首元素放入结果集
res.add(intervals.get(0));
// 遍历intervals，与结果集的最后一个元素比较，如果重叠，则删除原结果集的末尾元素
// 并new出合并后的intervals，放入结果集尾部。如果不重叠，则将遍历到的区间放入结果集尾部
for (int i = 1; i < intervals.size(); i++) {
// 取出结果集尾部元素
Interval i1 = res.get(res.size() - 1);
// 取出遍历到的结果集
Interval i2 = intervals.get(i);
// i1.end >= i2.start表示重叠,
if (i1.end >= i2.start) {
// 删除原结果集的末尾元素
res.remove(res.size() - 1);
// new出合并后的intervals，放入结果集尾部
int star = Math.min(i1.start, i2.start);
int end = Math.max(i1.end, i2.end);
res.add(new Interval(star, end));
// 不重叠，则将遍历到的区间放入结果集尾部
} else res.add(i2);
}
return res;
}
}
发表于 2023-11-03 16:40:43
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
ArrayList<Interval> sorted = new ArrayList<Interval>();
Interval last = new Interval(-1, -1);
Collections.sort(intervals,new Comparator<Interval>(){
@Override
public int compare(Interval i1,Interval i2){
if(i1.start-i2.start!=0){
return i1.start-i2.start;
}else return i2.end-i1.end;
}
});
for (Interval interval : intervals) {
if (last.start == -1 && last.end == -1) {
last.start = interval.start;
last.end = interval.end;
} else if (last.start < interval.start && last.end >= interval.start) {
last.end = Math.max(last.end,interval.end) ;
} else if (last.end < interval.start) {
sorted.add(new Interval(last.start, last.end));
last.start = interval.start;
last.end = interval.end;
}
}
if (last.start != -1 || last.end != -1) {
sorted.add(last);
}
return sorted;
}
}
发表于 2023-09-07 16:23:07
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
if(a.start == b.start){
return a.end < b.end ? - 1 : 1;
}
return a.start < b.start ? - 1 : 1;
}
});
int i = 0, j = 1;
while (j < intervals.size()) {
if (intervals.get(i).end < intervals.get(j).start) {
i++;
j++;
} else {
int end = Math.max(intervals.get(i).end, intervals.get(j).end);
int start = Math.min(intervals.get(i).start, intervals.get(j).start);
intervals.set(i, new Interval(start, end));
intervals.remove(j);
}
}
//Collections.sort(intervals,(Interval a,Interval b)->(a.start).compareTo(b.start));
return intervals;
}
}
为了原地排序，时间爆炸
发表于 2023-08-17 17:12:45
回复(0)
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* public Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
// write code here
if (intervals.size() == 0) {
return intervals;
}
// 先排序
intervals.sort(Comparator.comparingInt(obj -> obj.start));
ArrayList<Interval> list = new ArrayList<>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (int i = 1; i < intervals.size(); i++) {
Interval interval = intervals.get(i);
if (end >= interval.start) {
// 说明有重合
if (end < interval.end) {
end = interval.end;
}
continue;
}
// 不重合
Interval tem = new Interval(start, end);
list.add(tem);
start = interval.start;
end = interval.end;
}
// 最后一个
Interval tem = new Interval(start, end);
list.add(tem);
return list;
}
}
发表于 2023-08-09 22:11:32
回复(0)
问题信息
难度：
105条回答
1421收藏
29484浏览
通过挑战的用户
查看代码-
2023-03-10 13:59:15 -
2023-03-05 20:02:11 -
2023-03-04 16:26:47
-
2023-02-26 10:59:27
-
2023-02-24 20:59:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
