给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
数据范围：区间组数 
，区间内 的值都满足 
要求：空间复杂度 )
，时间复杂度 )
进阶：空间复杂度 )
，时间复杂度
[编程题]合并区间
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 ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
PriorityQueue<Interval> queue=new PriorityQueue<Interval>(new Comparator<Interval>(){
@Override
public int compare(Interval i1 ,Interval i2){
if(i1.start==i2.start){
return i1.end-i2.end;
}
return i1.start-i2.start;
}
});
for(int i=0;i<intervals.size();i++){
queue.add(intervals.get(i));
}
ArrayList<Interval> res=new ArrayList<>();
while(!queue.isEmpty()){
Interval interval=queue.poll();
while(!queue.isEmpty() && interval.end>=queue.peek().start){
interval.end=Math.max(interval.end ,queue.poll().end);
}
res.add(interval);
}
return res;
}
发表于 2024-03-03 14:11:51
回复(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)
作为新手的第一想法
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>(){
@Override
public int compare(Interval it1,Interval it2){
return it1.start - it2.start;
}
});
Iterator<Interval> it = intervals.iterator();
ArrayList<Interval> listResult = new ArrayList<>();
//获取第一个
Interval node = null,interval;
if (it.hasNext()){
node = it.next();
if(!it.hasNext()){
listResult.add(node);
}
}
//标记
int flag = 0;
while(it.hasNext()){
flag = 1;
interval = it.next();
//可以合并
if (interval.start >= node.start && interval.start <= node.end){
if(interval.end > node.end){
node.end = interval.end;
}
} else {
listResult.add(node);
node = interval;
}
}
if(flag == 1){
listResult.add(node);
}
return listResult;
}
}
发表于 2023-07-23 18:15:14
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类ArrayList
* @return Interval类ArrayList
*/
public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
// write code here
if(intervals == null) return new ArrayList<Interval>();
ArrayList<Interval> res = new ArrayList<Interval>();
int n = intervals.size();
int i = 0;
Collections.sort(intervals,(a,b)->{return a.start-b.start;});
while(i < n) {
int left = intervals.get(i).start;
int right = intervals.get(i).end;
while(i < n-1 && intervals.get(i+1).start <= right) {
right = Math.max(right,intervals.get(i+1).end);
i++;
}
res.add(new Interval(left,right));
i++;
}
return res;
}
}
发表于 2023-07-03 20:10:58
回复(0)
没啥难度，工作中也遇到过这种
import java.util.*;
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public static ArrayList<Interval> merge(ArrayList<Interval> intervals) {
intervals.sort((e1, e2) -> e1.start > e2.start ? 1 : -1);
ArrayList<Interval> list = new ArrayList<>();
for (Interval currentNode : intervals) {
if (list.isEmpty()) {
list.add(currentNode);
continue;
}
Interval endElement = list.get(list.size() - 1);
if (endElement.start <= currentNode.start &&
currentNode.start <= endElement.end) {
endElement.end = Math.max(endElement.end, currentNode.end);
continue;
}
list.add(currentNode);
}
return list;
}
}
发表于 2023-05-16 10:13:23
回复(0)
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if(intervals.size() == 0){
return intervals;
}
intervals.sort((o1, o2) -> o1.start - o2.start);
Interval before = intervals.get(0);
Iterator<Interval> it = intervals.iterator();
it.next();
while (it.hasNext()) {
Interval next = it.next();
if (before.end >= next.start) {
if (next.end >= before.end) {
before.end = next.end;
}
it.remove();
} else {
before = next;
}
}
return intervals;
}
}
发表于 2023-01-24 11:11:03
回复(0)
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals == null) {
return new ArrayList<>();
}
intervals.sort((o1, o2) -> o1.start - o2.start);
ArrayList<Interval> result = new ArrayList<>();
for (Interval interval : intervals) {
int resSize = result.size();
if (resSize > 0) {
Interval res = result.get(resSize - 1);
if (res.end >= interval.start) {
res.end = Math.max(interval.end, res.end);
continue;
}
}
result.add(interval);
}
return result;
}
}
发表于 2022-12-30 16:35:53
回复(0)
写得很烦
import java.util.*;
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if (intervals.size() == 0) {
return new ArrayList<>();
}
ArrayList<Interval> res = new ArrayList<>();
res.add(intervals.get(0));
for (int i = 1; i < intervals.size(); i++) {
res = inside(intervals.get(i), res);
}
return res;
}
ArrayList<Interval> inside(Interval newinterval,
ArrayList<Interval> hasinside) {
int i = 0;
for (; i < hasinside.size(); i++) {
Interval temp = hasinside.get(i);
if (newinterval.start > temp.end) {
continue;
}
if (newinterval.start >= temp.start) {
goend(i, hasinside, temp, newinterval);
break;
} else {
if (newinterval.end < temp.start) {
hasinside.add(i, newinterval);
return hasinside;
}
temp.start = newinterval.start;
goend(i, hasinside, temp, newinterval);
break;
}
}
if(i==hasinside.size()){
hasinside.add(newinterval);
}
return hasinside;
}
void goend(int i, ArrayList<Interval> hasinside, Interval temp,
Interval newinterval) {
int j = i;
for (; j < hasinside.size(); j++) {
if (hasinside.get(j).end > newinterval.end) {
break;
}
}
if (j < hasinside.size()) {
if (newinterval.end < hasinside.get(j).start) {
temp.end = newinterval.end;
j--;
} else {
temp.end = hasinside.get(j).end;
}
} else {
temp.end = newinterval.end;
j--;
}
while (j > i) {
hasinside.remove(j);
j--;
}
}
}
发表于 2022-11-18 22:32:48
回复(0)
import java.util.*;
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> res = new ArrayList<>();
if(intervals.size()==0) return res;
// 排序
intervals.sort((a,b)->a.start-b.start);
// 放入首值
res.add(intervals.get(0));
// 用于取索引
int count = 0;
for(int i=1;i<intervals.size();i++){
Interval curr = intervals.get(i);
Interval tmp = res.get(count);
if(curr.start<=tmp.end)
// 更新end值
tmp.end = Math.max(tmp.end, curr.end);
else {
res.add(curr);
count++;
}
}
return res;
}
}
发表于 2022-11-17 14:50:20
回复(1)
问题信息
难度：
95条回答
1213收藏
26094浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
