题意: 给出一个区间的集合, 请合并所有重叠的区间. https://leetcode-cn.com/problems/merge-intervals/
解题思路一: 使用排序, 开始时间从小至大排序.
- vector merge(vector& intervals) {
- sort(intervals.begin(),intervals.end()); // sort 是什么机制? 为什么能够对 vector> 直接 sort, 好强;
- if(intervals.size()<=1){
- return intervals;
- }
- auto p1=intervals.begin();
- auto p2=intervals.begin()+1;
- while(p2!=intervals.end()){
- // 考虑 p2[0] 和 p1[1] 的关系
- if((*p2)[0]<=(*p1)[1]){
- int tmp=max((*p2)[1],(*p1)[1]);
- (*p1)[1]=tmp;
- }
- else{
- p1++;
- p1->swap(*p2);
- }
- p2++;
- }
- intervals.erase(++p1,intervals.end());
- return intervals;
- }
来源: http://www.bubuko.com/infodetail-3394848.html