首页 > 代码库 > [LeetCode]56.Merge Intervals
[LeetCode]56.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]
.
【分析】
(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]
这里分三种情况:
a:[1,3] [2,6] -> [1,6] 第一个区间的end大于等于第二个区间的start,同时第二个区间的end大于第一个区间的end
b:[1,7] [2,4] -> [1,7] 第一个区间的end大于等于第二个区间的start,同时第二个区间的end小于第一个区间的end
c:[1,2] [3,4] -> [1,2] [3,4] 第一个区间的end小于第二个区间的start
【代码】
/********************************* * 日期:2015-01-14 * 作者: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; }
[LeetCode]56.Merge Intervals
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。