国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > [LeetCode]56.Merge Intervals

[LeetCode]56.Merge Intervals

来源:程序员人生   发布时间:2015-02-13 08:19:31 阅读次数:2192次

【题目】

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].

【分析】

(1)先将目标区间数组按X轴从小到大排序。例如:[2,3] [1,2] [3,9] ->[1,2] [2,3] [3,9]

(2)扫描排序后的目标区间数组,将这些区间合并成若干个互不相交的区间。例如 [2,3] [1,2] [4,9] ->[1,3]  [4,9]

这里分3种情况:

a:[1,3] [2,6]  -> [1,6]  第1个区间的end大于等于第2个区间的start,同时第2个区间的end大于第1个区间的end

b:[1,7] [2,4] -> [1,7]  第1个区间的end大于等于第2个区间的start,同时第2个区间的end小于第1个区间的end

c:[1,2] [3,4] -> [1,2] [3,4] 第1个区间的end小于第2个区间的start

【代码】

/********************************* * 日期:2015-01⑴4 * 作者:SJF0115 * 题目: 56.Merge Intervals * 网址:https://oj.leetcode.com/problems/merge-intervals/ * 结果:AC * 来源:LeetCode * 博客: **********************************/ #include <iostream> #include <algorithm> #include <vector> using namespace std; 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 cmp(const Interval& ina,const Interval& inb){ return ina.start < inb.start; } vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> result; int count = intervals.size(); if(count <= 1){ return intervals; }//if // x轴排序 sort(intervals.begin(),intervals.end(),cmp); // 合并 result.push_back(intervals[0]); // 斟酌3种情况 for(int i = 1;i < count;i++){ Interval preIn = result.back(); Interval curIn = intervals[i]; // [1,3] [2,6] if(curIn.start <= preIn.end && curIn.end > preIn.end){ preIn.end = curIn.end; result.pop_back(); result.push_back(preIn); }//if // [1,2] [3,4] else if(curIn.start > preIn.end){ result.push_back(curIn); } // [1,7] [2,3] 不用做任何事 }//for return result; } }; int main(){ Solution solution; Interval in1(1,2); Interval in2(4,6); Interval in3(8,10); Interval in4(15,18); vector<Interval> vec; vec.push_back(in1); vec.push_back(in2); vec.push_back(in3); vec.push_back(in4); // 合并 vector<Interval> v = solution.merge(vec); // 输出 for(int i = 0;i < v.size();i++){ Interval in = v[i]; cout<<"["<<in.start<<","<<in.end<<"]"<<endl; }//for return 0; }



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生