给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。
数据范围：区间列表长度满足 
， 区间的左右端点满足 
[编程题]插入区间
一个比较容易想到的思路是：先将新的区间连同原有的区间放到一个容器里，然后按区间的起点升序，且终点也升序进行二次排序，保证对于起点相同的区间而言，大区间排在后面。排好序后就可以对容器中的区间进行合并，遍历容器，不断将当前要加入到结果集中的区间与结果集中的最后一个区间进行对比，两者有重合区域时就将结果集的末尾区间修改成范围更大的。
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类一维数组
* @param newInterval Interval类
* @return Interval类一维数组
*/
public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
// write code here
if(Intervals.length == 0){
return new Interval[]{newInterval};
}
ArrayList<Interval> list = new ArrayList<>();
list.add(newInterval);
for(int i = 0; i < Intervals.length; i++){
list.add(Intervals[i]);
}
// 先对所有区间按起点升序终点也升序进行二次排序，这样可以保证相同起点的区间，更大的区间在后面
Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end);
// 用双端链表构建一个结果集
LinkedList<Interval> linkedlist = new LinkedList<>();
linkedlist.add(list.get(0));
for(int i = 1; i < list.size(); i++){
if(list.get(i).start <= linkedlist.getLast().end){
// 当前区间与最后一个加入的区间有重叠
if(list.get(i).end <= linkedlist.getLast().end){
// 当前区间已经被前面的区间囊括
continue;
}
// 合并区间
list.get(i).start = linkedlist.getLast().start;
linkedlist.removeLast();
linkedlist.add(list.get(i));
}else{
linkedlist.add(list.get(i));
}
}
Interval[] res = new Interval[linkedlist.size()];
Iterator<Interval> iterator = linkedlist.iterator();
int index = 0;
while(iterator.hasNext()){
res[index++] = iterator.next();
}
return res;
}
}
发表于 2021-12-11 14:54:06
回复(0)
解法一： 直接将 newInterval 加入容器，然后排序，再组装结果，发现重叠则合并即可，思路清晰，代码简洁：
public static Interval[] insertInterval(Interval[] intervals, Interval newInterval) {
// write code here
List<Interval> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort((o1, o2) -> o1.start == o2.start ? o1.end - o2.end : o1.start - o2.start);
// 遍历组装结果
ArrayList<Interval> resList = new ArrayList<>();
resList.add(list.get(0));
for (int i = 1; i < list.size(); i++) {
int start = list.get(i).start;
int end = list.get(i).end;
Interval last = resList.get(resList.size() - 1);
// 判断是否重叠
if (last.end >= start) {
resList.remove(resList.size() - 1);
resList.add(new Interval(last.start, Math.max(end, last.end)));
} else resList.add(list.get(i));
}
return resList.toArray(new Interval[0]);
}
} 解法二： 由于题目给的原始数组已经按区间大小排好序了，则转变思路，直接去寻找 newInterval 影响的区间有哪些，然后将影响后的区间范围重新赋值给 newInterval, 最后再遍历求出不重复的区间，但需要注意的是，如果想避免对最后的结果排序，就要考虑 newInterval 完全不重叠的情况下，是在头部还是在尾部，将其加入正确的位置即可；在中间时，判断区间不重叠就比较简单了，代码如下： public static Interval[] insertInterval(Interval[] intervals,
Interval newInterval) {
// write code here
if (intervals.length == 0) return new Interval[]{newInterval};
// 求出插入后的影响范围大小
for (Interval interval : intervals) {
// start 有交集
if (newInterval.start >= interval.start && newInterval.start <= interval.end)
newInterval.start = interval.start;
// end 有交集
if (newInterval.end >= interval.start && newInterval.end <= interval.end)
newInterval.end = interval.end;
}
ArrayList<Interval> res = new ArrayList<>();
// 判断是否在头部
if (newInterval.end < intervals[0].start)
res.add(0, newInterval);
// 判断是否在尾部
else if (newInterval.start > intervals[intervals.length - 1].end)
res.add(newInterval);
else
// 在中间，则添加合并后的区间
for (Interval interval : intervals) {
if (interval.end < newInterval.start || interval.start > newInterval.end)
res.add(interval);
else if (!res.contains(newInterval)) res.add(newInterval);
}
// 组装结果
return res.toArray(new Interval[0]);
} PS: 喝了半瓶老白干儿撸的代码，头现在还晕着 ，不足之处直接指出
发表于 2024-09-10 17:13:52
回复(1)
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
vector<Interval>ans;
if(Intervals.empty()){
ans.push_back(newInterval);
return ans;
}
Intervals.push_back(newInterval);
sort(Intervals.begin(),Intervals.end(),[](Interval a,Interval b){return a.start<b.start;});
for(int i=0;i<Intervals.size()-1;i++){
Interval temp=Intervals[i];
while(temp.end>=Intervals[i+1].start){
temp.end=max(temp.end,Intervals[i+1].end);
i++;
}
ans.push_back(temp);
}
if(ans.back().end>=Intervals.back().end){
return ans;
}else{
ans.push_back(Intervals.back());
return ans;
}
}
};
编辑于 2024-04-19 13:52:16
回复(0)
class Solution: def insertInterval(self , Intervals: List[Interval], newInterval: Interval) -> List[Interval]: # write code here if len(Intervals) == 0: return [newInterval] res = [] res.append(Intervals[0]) selected = False for i in range(len(Intervals)): if not selected: if self.is_interval_intersect(newInterval, res[-1]): res[-1].start = min(res[-1].start, newInterval.start) res[-1].end = max(res[-1].end, newInterval.end) selected = True if self.is_interval_intersect(res[-1], Intervals[i]): res[-1].start = min(res[-1].start, Intervals[i].start) res[-1].end = max(res[-1].end, Intervals[i].end) else: res.append(Intervals[i]) if not selected: res.append(newInterval) return res def is_interval_intersect(self, i1, i2): a1,b1 = i1.start,i1.end a2,b2 = i2.start,i2.end if a1 <= a2 <= b1&nbs***bsp;a1 <= b2 <= b1&nbs***bsp;a2 <= a1 <= b2: return True else: return False
发表于 2024-04-01 22:45:05
回复(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类一维数组
* @param newInterval Interval类
* @return Interval类一维数组
*/
public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
// write code here
Arrays.sort(Intervals, (i1, i2) -> {
if(i1.start == i2.start) {
return i1.end - i2.end;
}
return i1.start - i2.start;
});
int start = newInterval.start;
int end = newInterval.end;
List<Interval> list = new ArrayList<>();
int i = 0;
for(; i < Intervals.length; i++) {
Interval in = Intervals[i];
// 不能合并
if(start > in.end || end < in.start) {
list.add(new Interval(in.start, in.end));
continue;
}else {
start = Math.min(start, in.start);
end = Math.max(end, in.end);
}
}
list.add(new Interval(start, end));
Interval[] res = new Interval[list.size()];
for(int j = 0; j < res.length; j++) {
res[j] = list.get(j);
}
Arrays.sort(res, (i1, i2) -> {
if(i1.start == i2.start) {
return i1.end - i2.end;
}
return i1.start - i2.start;
});
return res;
}
}
编辑于 2024-02-10 14:16:46
回复(0)
class Solution {
public Interval[] insertInterval (Interval[] intervals, Interval newInterval){
ArrayList<Interval> list = new ArrayList<>();
for (Interval interval : intervals) {
if (newInterval.end < interval.start || newInterval.start > interval.end){
list.add(interval);
}else {
newInterval.start = Math.min(newInterval.start, interval.start);
newInterval.end = Math.max(newInterval.end, interval.end);
}
}
list.add(newInterval);
Interval[] array = list.toArray(new Interval[0]);
Arrays.sort(array, (o1, o2) -> o1.start - o2.start);
return array;
}
} Java解法 不相交区间正在加在返回结果中 相交的区间取[min(L1, L2), max(R1, R2)]即可
发表于 2022-04-06 20:55:33
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param Intervals Interval类vector
* @param newInterval Interval类
* @return Interval类vector
*/
vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
// write code here
int i = 0;
int n = Intervals.size();
int s = newInterval.start , e = newInterval.end;
vector<Interval> res;
while(i < n && Intervals[i].end < s){
res.push_back(Intervals[i]);
i++;
}
res.push_back(newInterval);
while(i < n && res.back().end >= Intervals[i].start){
res.back().start = min(Intervals[i].start,res.back().start);
res.back().end = max(Intervals[i].end,res.back().end);
i++;
}
while(i < n) {res.push_back(Intervals[i]);i++;}
return res;
}
};
发表于 2022-03-05 16:20:30
回复(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类一维数组
* @param newInterval Interval类
* @return Interval类一维数组
*/
public Interval[] insertInterval (Interval[] Intervals, Interval newInterval) {
// write code here
if(Intervals.length == 0){
return new Interval[]{newInterval};
}
ArrayList<Interval> list = new ArrayList<>();
list.add(newInterval);
for(int i = 0; i < Intervals.length; i++){
list.add(Intervals[i]);
}
// 先对所有区间按起点升序终点也升序进行二次排序，这样可以保证相同起点的区间，更大的区间在后面
Collections.sort(list, (a, b) -> a.start != b.start? a.start - b.start: a.end - b.end);
// 用双端链表构建一个结果集
LinkedList<Interval> linkedlist = new LinkedList<>();
linkedlist.add(list.get(0));
for(int i = 1; i < list.size(); i++){
if(list.get(i).start <= linkedlist.getLast().end){
// 当前区间与最后一个加入的区间有重叠
if(list.get(i).end <= linkedlist.getLast().end){
// 当前区间已经被前面的区间囊括
continue;
}
// 合并区间
list.get(i).start = linkedlist.getLast().start;
linkedlist.removeLast();
linkedlist.add(list.get(i));
}else{
linkedlist.add(list.get(i));
}
}
Interval[] res = new Interval[linkedlist.size()];
Iterator<Interval> iterator = linkedlist.iterator();
int index = 0;
while(iterator.hasNext()){
res[index++] = iterator.next();
}
return res;
}
}
发表于 2021-12-28 22:02:36
回复(0)
问题信息
难度：
9条回答
22收藏
1568浏览
通过挑战的用户
查看代码-
2022-09-16 01:43:42 -
2022-09-15 21:13:57 -
2022-09-15 15:44:50
-
2022-09-14 08:37:49
-
2022-09-14 01:11:18
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
