首页 > 代码库 > LeetCode: Merge Intervals [055]
LeetCode: Merge Intervals [055]
【题目】
Given an array of non-negative integers, you are initially positioned at the first index of the array.
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. 先对区间按开始值一级升序排列,然后按照结束值二级升序排列
2. 对排序后的区间依次合并即可
【代码】
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ bool compare(const Interval&o1, const Interval&o2){ if(o1.start<o2.start)return true; else if(o1.start==o2.start){ return o1.end<o2.end; } return false; } class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> result; int size=intervals.size(); if(size==0)return result; //排序 sort(intervals.begin(), intervals.end(),compare); //合并 Interval curInterval(intervals[0].start, intervals[0].end); for(int i=1; i<size; i++){ if(curInterval.end<intervals[i].start){ result.push_back(curInterval); curInterval=Interval(intervals[i].start, intervals[i].end); } else{ if(intervals[i].end>curInterval.end)curInterval.end=intervals[i].end; } } //别忘了最后一个区间 result.push_back(curInterval); return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。