本文主要是介绍LeetCode 题解(3):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]
.
题解:
/*** 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> temp;if( intervals.empty() )return temp;sort(intervals.begin(), intervals.end(), compare);vector<Interval>::iterator iter = intervals.begin();while(iter < intervals.end()-1){temp.push_back(*iter);if(iter->end >= (iter+1)->start){(iter+1)->start = min(iter->start, (iter+1)->start);(iter+1)->end = max(iter->end, (iter+1)->end);temp.pop_back();}iter++;}temp.push_back(*iter);return temp;}private:static bool compare(const Interval &t1, const Interval &t2){return t1.start < t2.start;}
};
测试用例:
#include <vector>
#include <cassert>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>using namespace std;int main( int argc, char* argv[] )
{Interval a(2, 3), b(4, 5), c(6, 7), d(8, 9), e(1, 10);vector<Interval> intervals;intervals.push_back(d);intervals.push_back(c);intervals.push_back(b);intervals.push_back(a);intervals.push_back(e);Solution s;vector<Interval> f = s.merge(intervals);return 0;
}
这篇关于LeetCode 题解(3):Merge Intervals的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!