题解 | #插入区间#

//给 n 个信封的长度和宽度。如果信封 a 的长和宽都小于信封 b ，那么信封 a 可以放到信封 b 里，请求出信封最多可以嵌套多少层。

//数据范围： 1 \le n \le 2\times10^31≤n≤2×103 ， 1 \le lettersi, lettersi \le 2\times10^31≤lettersi,lettersi≤2×103

/**
 * struct Interval {
 *    int start;
 *    int end;
 *    Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Intervals Interval类vector 
     * @param newInterval Interval类 
     * @return Interval类vector
     */
//自定义比较器
    static bool cmp(Interval &a,Interval &b){
        if(a.start==b.start){
            return a.end<b.end;
        }
        return a.start<b.start;
    }
    vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
        // write code here
        vector<Interval> res;
        Intervals.push_back(newInterval);
        int n=Intervals.size();
        sort(Intervals.begin(),Intervals.end(),cmp);//对数据进行排序
        int temp=0;
        int end=Intervals[0].end,first=Intervals[0].start;
        for(int i=1;i<n;i++){
            if(end>=Intervals[i].start){
                end=max(end,Intervals[i].end);//贪心策略取最远能达到的地方
            }else{
                Interval ans;
                ans.start=first;
                ans.end=end;              
                res.push_back(ans);
                int j=res.size();//因为不满足之前if判断，first和end将进行判断从而进入下一个测试区间
                if(j>0&&res[j-1].end==end&&res[j-1].start==first){
                first=Intervals[i].start;
                end=Intervals[i].end;
                continue;
                }     
            }
        }//将最后一个区间放入答案中
        Interval ans;
        ans.start=first;
        ans.end=end;
        res.push_back(ans);    
        return res;
    }
};