首页 > 代码库 > 【LeetCode】Merge Intervals
【LeetCode】Merge Intervals
Merge Intervals
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].
记返回数组为ret。
先对start排序。
然后对每两个interval（记为a,b），判断是否需要合并。
如果不需要合并（没有交集），则把a装入ret，将b继续往后。
如果需要合并（有交集），则把结果c继续往后。
这题本身是不难的，但是有两个细节：
1、compare函数中，如果是升序，必须是<而不是<=
解释：参考http://www.cplusplus.com/reference/list/list/sort/，比较必须产生strick weak ordering。
对于strick weak ordering 可以参考http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering/981299#981299
的详细说明。
总之，如果a,b不等，那么compare(a,b)和compare(b,a)其中之一为true，另一为false。
如果a,b相等，则都应该为false。
2、compare函数必须声明为静态成员函数或者全局函数，不能作为普通成员函数
解释：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法在sort中调用非静态成员函数。
可以把compare改成静态或者全局函数，使之不依赖于具体对象。
/** * 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: static bool compare(Interval a, Interval b) {//non-static member function cannot pass to std::sort return a.start < b.start; } vector<Interval> merge(vector<Interval> &intervals) { if(intervals.empty() || intervals.size()==1) return intervals; vector<Interval> ret; //sort according to start sort(intervals.begin(), intervals.end(), compare); //at least two intervals Interval last = intervals[0]; int i = 1; while(i < intervals.size()) { Interval cur = intervals[i]; if(last.end < cur.start) { ret.push_back(last); last = cur; i ++; } else {//last.end >= cur.start if(last.end <= cur.end) { Interval newInt; newInt.start = last.start; newInt.end = cur.end; last = newInt; i ++; } else {//cur is totally enclosed by last i ++; } } } ret.push_back(last); return ret; }};
【LeetCode】Merge Intervals
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。