首页 > 代码库 > [LeetCode] Merge Intervals 排序sort
[LeetCode] Merge Intervals 排序sort
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Show Tags
Array Sort这题其实想好思路很好解决，对于框，如果下个框开始在 其中间，则连在一起，否则单独为一个，这需要按start 排序便可以了，因为类中写自定义比较函数比较麻烦，所以一次写了好几个。
- 按start 排序
- 初始化变量curstart,curend,记录当前窗的位置。
- 与下个窗比较，如果其start < curend，更新 curend。
- 否则加入ret，并跟新curstart,curend
- 遍历结束，加入最后的窗。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 /** 7 * Definition for an interval. 8 */ 9 struct Interval {10 int start;11 int end;12 Interval() : start(0), end(0) {}13 Interval(int s, int e) : start(s), end(e) {}14 };15 16 class Solution {17 public:18 vector<Interval> merge(vector<Interval> &intervals) {19 sort(intervals.begin(),intervals.end(),20 [] (Interval i1,Interval i2)21 {return i1.start<i2.start; });22 23 /// sort(intervals.begin(),intervals.end(),help_fun);24 25 /** struct my_cmp{26 bool operator ()(Interval i1,Interval i2){27 return i1.start<i2.start;28 }29 }my_cmp1;30 sort(intervals.begin(),intervals.end(),my_cmp());31 sort(intervals.begin(),intervals.end(),my_cmp1);32 */33 34 // for(int i=0;i<intervals.size();i++){35 // cout<<intervals[i].start<<" "<<intervals[i].end<<endl;36 // }37 vector<Interval> ret;38 if(intervals.size()<1) return ret;39 int curStart=intervals[0].start,curEnd=intervals[0].end;40 for(int i=1;i<intervals.size();i++){41 if(curEnd>=intervals[i].start){42 if(intervals[i].end>curEnd) curEnd=intervals[i].end;43 continue;44 }45 ret.push_back(Interval(curStart,curEnd));46 curStart = intervals[i].start;47 curEnd = intervals[i].end;48 }49 ret.push_back(Interval(curStart,curEnd));50 return ret;51 }52 53 static bool help_fun(Interval i1,Interval i2)54 {55 return i1.start<i2.start;56 }57 };58 59 int main()60 {61 vector<Interval> intervals={Interval(8,10),62 Interval(2,6),63 Interval(1,3),64 Interval(15,18)};65 Solution sol;66 vector<Interval> ret = sol.merge(intervals);67 68 for(int i=0;i<ret.size();i++){69 cout<<ret[i].start<<" "<<ret[i].end<<endl;70 }71 return 0;72 }
[LeetCode] Merge Intervals 排序sort
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。