[leetcode/matrix](sort)Insert Interval(库函数sort的运用)

拼搏现实的明天。 2021-09-28 08:10 154阅读 0赞

### 库函数sort的运用 ###

*   *  题干：
     *  题解
     *  代码
     *  总结

## 题干： ##

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
    Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval \[4,8\] overlaps with \[3,5\],\[6,7\],\[8,10\].  
Please submit a cpp file with the implementation of function

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval)

you can start like this:

vector<Interval> Solution::insert(vector<Interval>& intervals, Interval newInterval) {}

## 题解 ##

① 使用sort进行代码排序，cmp比较条件是，start小的排前面  
② 根据intervals里面end的情况决定直接修改最后一个intervals的end还是push\_back进去

## 代码 ##

#include"Solution.h"
    #include<algorithm>
    using namespace std;
    static bool cmp(Interval& a, Interval& b){ 
    	return a.start<b.start; //按照左端点的顺序排队 
    }
    
    vector<Interval> Solution::insert(vector<Interval>& intervals, Interval newInterval) { 
    	vector<Interval> ret; //要返回的区间
    	intervals.push_back(newInterval);
    	sort(intervals.begin(),intervals.end(),cmp);
    	
    	int count=0;//记录区间的数目
    	ret.push_back(intervals[0]);
    	
    	int size=intervals.size();
    	
    	for(int i=1;i<size;i++){ 
    		int& end=ret[count].end;
    		
    		if(intervals[i].end<=end){ 
    			continue;
    		}
    		else{ 
    			if(intervals[i].start<=end){ 
    				end=intervals[i].end;
    			}
    			else{ 
    				count++;
    				ret.push_back(intervals[i]);
    			}
    		}
    	} 
    	
    	return ret;
    }

## 总结 ##

刚开始想着分情况，start，end分别落在区间里和区间外的情况，后来感觉考虑的情形太多有点乱了。  
这个方法的好处是先根据start来排序，然后再根据end进行处理，简化了分类情况