题解 | #插入区间#

/**
 * 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.start < b.start;
        return a.end < b.end;
    }
    vector<Interval> insertInterval(vector<Interval>& Intervals, Interval newInterval) {
        // write code here
        vector<Interval> res;
        Intervals.push_back(newInterval);
        sort(Intervals.begin(), Intervals.end(), cmp); // 排序
        int pre_s = Intervals[0].start;
        int pre_e = Intervals[0].end;
        res.push_back(Intervals[0]);
        for(int i = 1; i < Intervals.size(); i++) {
            int s = Intervals[i].start;
            int e = Intervals[i].end;
            // 分三种情况考虑，同时更新pre_s和pre_e
            if(pre_e < s ) {
                res.push_back(Intervals[i]);
                pre_s = s;
                pre_e = e;
            }
            else if(s <= pre_e && e >= pre_e) {
                res.pop_back();
                Intervals[i].start = pre_s;
                pre_e = e;
                res.push_back(Intervals[i]);
            }
        }
        return res;
    }
};