zsh-89/Insert Interval.cpp

## Insert Interval.cpp
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> insert(vector<Interval> &v, Interval x) {
        vector<Interval> ans;  bool in = false;  int N = v.size();
        for (int i = 0; i < N;) {
            if (in==false && x.start < v[i].start) {
                ans.push_back(x);  in = true;
            } else {
                ans.push_back(v[i]);
                ++i;
            }
        }
        if (in == false) ans.push_back(x);

        int k = 0;  Interval t = ans[0];
        for (int i = 1; i < N+1; ++i) {
            if (ans[i].start <= t.end) {
                t.end = max(t.end, ans[i].end);
            } else {
                ans[k++] = t;  t = ans[i];
            }
        }
        ans[k++] = t;
        for (int i = 0; i < N+1-k; ++i)
            ans.pop_back();
        return ans;
    }
};