给出一组区间,请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
数据范围:区间组数 ,区间内 的值都满足
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
[[10,30],[20,60],[80,100],[150,180]]
[[10,60],[80,100],[150,180]]
[[0,10],[10,20]]
[[0,20]]
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) { // 排序后再处理,更方便,后续只要关注 end1 和 [start2,end2] 的关系就行 Collections.sort(intervals,(o1,o2)->{ if(o1.start != o2.start){ return o1.start-o2.start; }else{ return o1.end-o2.end; } }); for(int i=0;i<intervals.size()-1;i++){ // end1 >= end2,说明第二个区间都包裹在第一个区间里,直接移除掉第二个区间 if(intervals.get(i).end >= intervals.get(i+1).end){ intervals.remove(i+1); i--; } // end2 > end1 >= star2,说明这两个区间可以首尾合并,end1 = end2,直接移除第二个区间 else if(intervals.get(i).end >= intervals.get(i+1).start){ intervals.get(i).end = intervals.get(i+1).end; intervals.remove(i+1); i--; } // 其他情况都不需要处理 } return intervals; } }
/** * 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> ans; sort(begin(intervals), end(intervals), [](const auto& a, const auto& b) { return a.start < b.start; }); for (const auto& interval : intervals) { if (ans.empty() || interval.start > ans.back().end) ans.emplace_back(interval); else ans.back().end = max(ans.back().end, interval.end); } return ans; } };
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<>(); Collections.sort(intervals, new Comparator<Interval>() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); int i = 0; while(i < intervals.size()) { int left = intervals.get(i).start; int right = intervals.get(i).end; while(i < intervals.size()-1 && right >= intervals.get(i+1).start){ right = Math.max(right,intervals.get(i+1).end); i++; } res.add(new Interval(left, right)); i++; } return res; } }
import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { ArrayList<Interval> res = new ArrayList<>(); if (intervals.size() == 0) { return res; } Collections.sort(intervals); res.add(intervals.get(0)); for (int i = 1; i < intervals.size(); i++) { Interval tmp = intervals.get(i); Interval pre = res.get(res.size() - 1); if (tmp.start <= pre.end) { if (tmp.end <= pre.end) { continue; } else { res.remove(res.size() - 1); res.add(new Interval(pre.start, tmp.end)); } } else { res.add(tmp); } } return res; } public static void main(String[] args) { Solution s = new Solution(); ArrayList<Interval> intervals = new ArrayList<>(); // intervals.add(new Interval(10, 30)); // intervals.add(new Interval(20, 60)); // intervals.add(new Interval(80, 100)); // intervals.add(new Interval(150, 180)); intervals.add(new Interval(1,4)); intervals.add(new Interval(0,4)); s.merge(intervals); } } class Interval implements Comparable<Interval> { int start; int end; Interval() { start = 0; end = 0; } Interval(int s, int e) { start = s; end = e; } @Override public int compareTo(Interval o) { if (this.start == o.start) { return this.end > o.end ? 1 : -1; } return (this.start > o.start) ? 1 : -1; } }
/** * 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; } };
1.先将Interval数组按照start、end从小到大进行排序;
2.设置指针i,从头遍历到intervals.size() - 1,当intervals.get(i).end >= intervals.get(i).start时候,将这两个元素进行合并,然后更新最大的end,以便接下来继续遍历比较;
3.如果结束循环的时候,i == intervals.size() - 1,那么需要将intervals.get(i)加入到结果集合中。
import java.util.ArrayList; import java.util.Collections; /** * 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<>(); Collections.sort(intervals, (o1, o2) -> o1.start != o2.start ? o1.start - o2.start : o1.end - o2.end); int i = 0; while (i < intervals.size() - 1) { int left = intervals.get(i).start; int right = intervals.get(i).end; while (i < intervals.size() - 1 && intervals.get(i + 1).start <= right) { right = Math.max(right, intervals.get(i + 1).end); i++; } res.add(new Interval(left, right)); i++; } if (i == intervals.size() - 1) { res.add(intervals.get(i)); } return res; } }
/**
* 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;
}
};
/** * 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; } }
#include<math.h> bool comp(const Interval &in1,const Interval &in2){ if(in1.start==in2.start){ return in1.end<in2.end; }else{ return in1.start<in2.start; } } class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { sort(intervals.begin(),intervals.end(),comp); //按start升序排序 vector<Interval> res; int len = intervals.size(); for(int i=0;i<len;i++){ if(res.empty()){ res.push_back(intervals[i]); }else{ Interval last = res.back(); if(last.end>=intervals[i].start){ //需要进行合并 res.pop_back(); last.end = max(last.end,intervals[i].end); res.push_back(last); }else{ res.push_back(intervals[i]); } } } return res; } };
/** * 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; } };
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; }
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; } }
// 想法很简单,先排个序,按照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; } }
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; } }
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; } };
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
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
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; } }
//按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; }