学步园

Merge Intervals  是典型的贪心算法，通过对段进行开始时间排序，然后遍历，每次判断是否可以合并，如不可合并，则加入新的段

 bool compare(const Interval &a,const Interval &b){
     return (a.start<b.start);
     }
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        int len=intervals.size();
        if(len<=1)return intervals;
        vector<Interval>ans;
        sort(intervals.begin(),intervals.end(),compare);
        ans.push_back(intervals[0]);
        for(int i=1;i<len;++i){
            if(intervals[i].start<=ans[ans.size()-1].end){
                  if(intervals[i].end>ans[ans.size()-1].end)
                            ans[ans.size()-1].end=intervals[i].end;
            }
            else ans.push_back(intervals[i]);
        }
    return ans;
    }
};

与上一题差别不大，只需要稍加修改即可

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        int len=intervals.size();
        vector<Interval>ans;
        if(len==0){ans.push_back(newInterval);return ans;}
        //sort(intervals.begin(),intervals.end(),compare);
        intervals.push_back(newInterval);
        int i=len-1;
        while(i>=0){
            if(intervals[i].start>intervals[i+1].start){
                Interval t=intervals[i+1];
                intervals[i+1]=intervals[i];
                intervals[i]=t;
                i--;
            }
            else break;
        }
        ans.push_back(intervals[0]);
        for(int i=1;i<=len;++i){
            if(intervals[i].start<=ans[ans.size()-1].end){
                  if(intervals[i].end>ans[ans.size()-1].end)
                            ans[ans.size()-1].end=intervals[i].end;
            }
            else ans.push_back(intervals[i]);
        }
    return ans;
    }
};