给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
//"区间"定义
class Interval {
int start; //起点
int end; //终点
}
数据范围：区间组数 
，区间内 的值都满足 
要求：空间复杂度 )
，时间复杂度 )
进阶：空间复杂度 )
，时间复杂度
[编程题]合并区间
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size() <= 1)
return intervals;
vector<Interval> vec;
sort(intervals.begin(),intervals.end(),[](Interval a,Interval b){return a.start < b.start;});
Interval tmp = intervals[0];
for(int i = 1; i < intervals.size(); ++i)
{
if(tmp.end < intervals[i].start)
{
vec.push_back(tmp);
tmp = intervals[i];
}
else
tmp.end = max(intervals[i].end,tmp.end);
}
vec.push_back(tmp);
return vec;
}
};
发表于 2019-12-19 15:03:53
回复(0)
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
int s=intervals.size();
if(s==0) return intervals;
for(int i=0;i<s;++i){
int m=intervals[i].start;
int tmp=i;
for(int j=i;j<s;++j){
if(intervals[j].start<m){
m=intervals[j].start;
tmp=j;
}
}
int temp=intervals[i].start;
intervals[i].start=intervals[tmp].start;
intervals[tmp].start=temp;
temp=intervals[i].end;
intervals[i].end=intervals[tmp].end;
intervals[tmp].end=temp;
}
for(int i=0;i<intervals.size()-1;++i){
if(intervals[i].start==intervals[i+1].start){
intervals.erase(intervals.begin()+(intervals[i].end>intervals[i+1].end?i+1:i));
--i;
}
else if(intervals[i].end>=intervals[i+1].start){
intervals[i].end=(intervals[i].end>intervals[i+1].end?intervals[i].end:intervals[i+1].end);
intervals.erase(intervals.begin()+i+1);
--i;
}
}
return intervals;
}
};
发表于 2018-08-09 15:37:47
回复(0)
/**
* 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; }
* }
*/
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if(intervals==null || intervals.size()<=1){
return intervals;
}
//对链表的start进行升序排序
Comparator<Interval> comparator = new Comparator<Interval>(){
public int compare(Interval s1,Interval s2){
return s1.start-s2.start;
}
};
Collections.sort(intervals,comparator);
//
for(int i=1;i<intervals.size();i++){
if(intervals.get(i).start>intervals.get(i-1).end){
}else{
int maxEnd = Math.max(intervals.get(i-1).end, intervals.get(i).end);
Interval temp = new Interval(intervals.get(i-1).start,maxEnd);
intervals.set(i-1, temp);
intervals.remove(i);
i--;
}
}
return intervals;
}
}
发表于 2016-03-17 17:08:49
回复(0)
function merge( $intervals)
{
// write code here
$total_intervals = count($intervals);
$new_intervals = [];
print_r($new_intervals);
for($i = 0; $i < $total_intervals; $i++){
$start = $intervals[$i]->start;
$end = $intervals[$i]->end;
for ($j = $i+1; $j < $total_intervals; $j++){
if($end > $intervals[$j]->start){
$end = $intervals[$j]->end;
continue;
}
break;
}
array_push($new_intervals, [$start, $end]);
$i = $j-1;
}
return $new_intervals;
}
{
// write code here
$total_intervals = count($intervals);
$new_intervals = [];
print_r($new_intervals);
for($i = 0; $i < $total_intervals; $i++){
$start = $intervals[$i]->start;
$end = $intervals[$i]->end;
for ($j = $i+1; $j < $total_intervals; $j++){
if($end > $intervals[$j]->start){
$end = $intervals[$j]->end;
continue;
}
break;
}
array_push($new_intervals, [$start, $end]);
$i = $j-1;
}
return $new_intervals;
}
发表于 2021-09-26 14:46:53
回复(0)
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
/*
思路：
注意先对数组进行排序
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> v;
int n = intervals.size();
if (0 == n) {
return v;
}
if (1 == n) {
v.push_back(intervals[0]);
return v;
}
sort(intervals.begin(),intervals.end(), compare_Interval);
Interval temp = intervals[0];
int i = 1;
while (i < n) {
if (temp.end < intervals[i].start) {
v.push_back(temp);
temp = intervals[i];
++i;
if (i == n) {
v.push_back(temp);
}
}
else {
temp.start = min(temp.start, intervals[i].start);
temp.end = max(temp.end, intervals[i].end);
++i;
if (i == n) {
v.push_back(temp);
}
}
}
return v;
}
static int compare_Interval(Interval val1, Interval val2){
return val1.start < val2.start;
}
};
编辑于 2017-11-29 22:15:05
回复(0)
static bool comp(const Interval& a,const Interval& b){
return (a.start<= b.start);
}
vector<Interval> merge(vector<Interval> &intervals) {
if(intervals.size()==0)
return intervals;
sort(intervals.begin(),intervals.end(),comp);
vector<Interval> res;
res.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++){
if(intervals[i].start>res.back().end)
res.push_back(intervals[i]);
else{
res.back().end=std::max(intervals[i].end,res.back().end);
}
}
return res;
}
发表于 2017-11-06 15:53:36
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
if(intervals.size() < 2) return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
if(o1.start == o2.start) return o1.end < o2.end ? - 1 : 1;
return o1.start < o2.start ? - 1 : 1;
}
});
ArrayList<Interval> list = new ArrayList<>();
list.add(intervals.get(0));
for (int i = 1; i < intervals.size(); i ++) {
Interval cur = intervals.get(i);
Interval ready = list.get(list.size() - 1);
if(cur.start <= ready.end) {
ready.end = cur.end > ready.end ? cur.end : ready.end;
list.remove(list.size() - 1);
list.add(ready);
} else list.add(cur);
}
return list;
}
}
发表于 2017-03-25 16:25:38
回复(0)
// 想法很简单，先排个序，按照start的升序，然后依次和后面的interval比较有没有交集
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> list = new ArrayList<>();
if(intervals == null)
return list;
if(intervals.size() <= 1)
return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval int1, Interval int2){
return int1.start - int2.start;
}
});
Interval cur = intervals.get(0);
for(int i = 1; i < intervals.size(); i++){
if(cur.end >= intervals.get(i).start){
cur.start = Math.min(cur.start, intervals.get(i).start);
cur.end = Math.max(cur.end, intervals.get(i).end);
if(i == intervals.size() - 1)
list.add(cur);
}
else{
list.add(cur);
cur = intervals.get(i);
if(i == intervals.size() - 1)
list.add(cur);
}
}
return list;
}
}
发表于 2017-05-15 14:51:03
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
return o1.start-o2.start;
}
});
for (int i = 1; i < intervals.size(); i++) {
int preStart = intervals.get(i - 1).start;
int preEnd = intervals.get(i - 1).end;
int curStart = intervals.get(i).start;
int curEnd = intervals.get(i).end;
if (curStart <= preEnd) {
intervals.set(i, new Interval(preStart, Math.max(preEnd, curEnd)));
intervals.set(i - 1, null);
}
}
while (intervals.remove(null)) ;
return intervals;
}
}
发表于 2017-11-22 18:47:42
回复(3)
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
int l = intervals.size();
if(l==0)
return result;
sort(intervals.begin(), intervals.end(), cmp);
result.push_back(intervals[0]);
for(int i=1;i<l;i++)
{
if(result.back().end >= intervals[i].start)
result.back().end = max(result.back().end, intervals[i].end);
else
result.push_back(intervals[i]); } return result;
}
static bool cmp(const Interval &a, const Interval &b)
{
return a.start < b.start; }
};
发表于 2017-09-27 07:47:43
回复(2)
class Solution:
def merge(self , intervals: List[Interval]) -> List[Interval]:
if not intervals:
return []
intervals.sort(key=lambda x: x.start)
res = [intervals[0]]
for i in intervals[1:]:
if res[-1].end < i.start:
res.append(i)
elif res[-1].end < i.end:
res[-1].end = i.end
return res
发表于 2022-05-26 20:59:39
回复(0)
class Solution: def merge(self , intervals ): # write code here intervals.sort(key=(lambda elme:elme.start)) res = [] for i in range (len(intervals)): if res == []: res.append(intervals[i]) else: if res[-1].end >= intervals[i].start : res[-1].end = max(intervals[i].end, res[-1].end) else: res.append(intervals[i]) return res
发表于 2021-09-02 00:31:11
回复(0)
import java.util.*;
public class Solution {
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> res=new ArrayList<Interval>();
if(intervals.size()==0||intervals==null)
return res;
Collections.sort(intervals, (a,b) -> a.start - b.start);
for(int i=1;i<intervals.size();i++)
{
if(intervals.get(i).start<=intervals.get(i-1).end)
{
intervals.get(i).start=intervals.get(i-1).start;
intervals.get(i).end=Math.max(intervals.get(i).end,intervals.get(i-1).end);
}
else
res.add(intervals.get(i-1));
}
res.add(intervals.get(intervals.size()-1));
return res;
}
}
编辑于 2020-01-23 19:21:24
回复(0)
//按start进行排序，然后一个个的加到结果res中。
//如果待加入节点的start <= res.back().end 说明相交，直接更新end，取节点end和当res.back().end中的较大值。
//如果start > res.back()则不相交 直接加入res中。
//第一个节点，也直接加入res中
vector<Interval> merge(vector<Interval> &intervals)
{
sort(intervals.begin(), intervals.end(),[](Interval x, Interval y){return x.start < y.start;});
vector<Interval> res;
for (int i = 0; i < (int)intervals.size(); i++)
{
if (i == 0 || intervals[i].start > res.back().end)
{
res.push_back(intervals[i]);
}
else
{
res.back().end = max(intervals[i].end, res.back().end);
}
}
return res;
}
发表于 2019-08-20 11:11:53
回复(0)
插旗问题
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
map <int, int> ss;
for(auto &c : intervals) {
ss[c.start]++;
ss[c.end]--;
}
vector <Interval> ans;
int cnt = 0, l;
for(auto &[k, v] : ss) {
if(!cnt) l = k;
cnt += v;
if(!cnt) ans.push_back(Interval(l, k));
}
return ans;
}
};
发表于 2022-03-12 20:07:28
回复(0)
和大部分人的代码不一样，没有定义两个类，思路却容易理解
class Solution: def merge(self , intervals ): intervals.sort()#按第一个数字排序以防输入的区间顺序错乱 list1=[] while len(intervals)>1:#为了使后续语句intervals[1][0]不出现越界错误，故设置长度大于1 if intervals[0][1]<intervals[1][0]:#前一个区间的上界小于后一个区间的下界，说明两个区间没有交集，直接添加 list1.append(intervals[0]) intervals.pop(0)#添加完成删除该区间 else:#否则两个区间有交集 intervals[0]=[min(intervals[0][0],intervals[1][0]),max(intervals[0][1],intervals[1][1])]#取两个区间的下界的最小值作为合并后区间的下界，取两个区间的上界的最大值作为合并后区间的上界，即完成两个区间的并集 intervals.pop(1)#合并后intervals的第一个元素用合并后的区间替换，那么参与合并的第二个元素（下标为1）也应该要删除 list1.append(intervals[0])#intervals还剩一个元素即退出循环体，故剩下的一个元素需要添加进来 list1=map(str,list1)#将列表元素的数据类型由整型转化为字符串，才能使用下面的join语句，否则报错 return ",".join(list1)#返回列表的所有元素，即去掉中括号后的列表 #print(Solution().merge([[18,18],[1,2],[8,10],[4,11],[0,8],[19,22]]))
发表于 2020-09-19 18:13:08
回复(1)
class Solution {
public:
// 先按照start从小到大时间轴排序，有重叠部分则进行合并
static bool compare(const Interval &a,const Interval &b)
{
return (a.start < b.start);
}
vector<Interval> merge(vector<Interval> &intervals)
{
vector<Interval> res;
int len = intervals.size();
if(len==0) return res;
sort(intervals.begin(),intervals.end(),compare);
res.push_back(intervals[0]);
for(int i=1;i<len;i++)
{
if(res.back().end >= intervals[i].start)
res.back().end = max(res.back().end,intervals[i].end);
else
res.push_back(intervals[i]);
}
return res;
}
};
发表于 2017-07-08 15:53:53
回复(2)
/**
* struct Interval {
* int start;
* int end;
* Interval(int s, int e) : start(start), end(e) {}
* };
*/
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param intervals Interval类vector
* @return Interval类vector
*/
vector<Interval> merge(vector<Interval>& intervals) {
// write code here
vector<int>dpl(2e5 + 10,0);
vector<int>dpr(2e5 + 10,0);
vector<Interval>ans;
Interval A;
for(auto [l,r] : intervals)
{
dpl[l] += 1;
dpr[r] += 1;
}
int sum = 0;
int l;
for(int i = 0; i <= 2e5; i ++ )
{
if(!sum && dpl[i]) l = i;
sum += dpl[i] - dpr[i];
if(!sum && dpr[i])
{
A.start = l;
A.end = i;
ans.push_back(A);
}
}
return ans;
}
};
发表于 2024-08-16 20:26:19
回复(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)
问题信息
难度：
318条回答
1329收藏
27837浏览
通过挑战的用户
查看代码-
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号
