首页 > 代码库 > [LeetCode] Merge Intervals
[LeetCode] 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].
在LeetCode“Insert Interval”的基础上写的代码：
/** * 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) { int len = intervals.size(); vector<Interval> res; for(int i=0;i<len;i++){ res = insert(res,intervals[i]); } return res; }private: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval> result; Interval temp; int len = intervals.size(); if(len==0){ //特殊情况，intervals是空时直接可以得到结果 result.push_back(newInterval); return result; } int startIndex,endIndex; int i,startflag=0,endflag=0; for(i = 0;i<len;){ if(intervals[i].start<=newInterval.start && intervals[i].end >= newInterval.end){//新区间在某个区间内 return intervals; }else if(startflag == 0 && intervals[i].start > newInterval.end ){//新区间在所有区间外，在某个区间之前 result.push_back(newInterval); startflag = 1; endflag = 1; break; }else if(intervals[i].end < newInterval.start && i!=len-1){//新区间的起点在此区间之后 result.push_back(intervals[i]); i++; }else if(startflag == 0 && newInterval.start < intervals[i].start && newInterval.end >= intervals[i].start && newInterval.end <= intervals[i].end){//新区间的起点在此区间之前，终点在此区间之间 startflag = 1; endflag = 1; temp.start = newInterval.start; temp.end = intervals[i].end; result.push_back(temp); i++; break; }else if(startflag == 0 && newInterval.start < intervals[i].start && newInterval.end > intervals[i].end){ //新区间的起点在此区间之前，终点超出此区间 startflag = 1; temp.start = newInterval.start; }else if(startflag == 0 && newInterval.start >= intervals[i].start && newInterval.start <= intervals[i].end && newInterval.end > intervals[i].end){//新区间的起点在此区间之间，终点超出此区间 startflag = 1; temp.start = intervals[i].start; }else if(startflag == 0 && i==len-1 && intervals[i].end< newInterval.start){//新区间在最后一个区间外 result.push_back(intervals[i]); result.push_back(newInterval); return result; } if(startflag==1 && endflag==0 && i==len-1 && newInterval.end >intervals[i].end){//新区间的终点在最后一个区间之后 temp.end = newInterval.end; endflag = 1; i++; result.push_back(temp); return result; }else if(startflag==1 && endflag==0 && newInterval.end > intervals[i].end){//新区间的终点越过此区间 i++; continue; }else if(startflag==1 && endflag==0 && newInterval.end < intervals[i].start){//新区间的终点在此区间之前 endflag = 1; temp.end = newInterval.end; result.push_back(temp); break; }else if(startflag==1 && endflag==0 && newInterval.end >= intervals[i].start && newInterval.end <= intervals[i].end){//新区间的终点在此区间之间 endflag = 1; temp.end = intervals[i].end; i++; result.push_back(temp); break; } }//end for while(i<len){ result.push_back(intervals[i++]); } return result; }//end func};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。