[LeetCode] Insert Interval

Insert Interval

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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

方法：高端方法，线段树！不过我忘了怎么写～～因此写点简单的方法。

 

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
#include <algorithm>
using namespace std;

int cmp(const Interval& a, const Interval& b) {return a.end < b.end;}
int cmp2(const Interval& a, const Interval& b) {return a.start < b.start;}

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval>::iterator it;
        it = lower_bound(intervals.begin(), intervals.end(), 
            Interval(0, newInterval.start), cmp);
        if (it == intervals.end()) {
            vector<Interval> res(intervals.begin(), intervals.end());
            res.push_back(newInterval);
            sort(res.begin(), res.end(), cmp2);
            return res;
        } else {
            // newInterval.start <= it.end
            if (it->start > newInterval.end) {
                vector<Interval> res(intervals.begin(), intervals.end());
                res.push_back(newInterval);
                sort(res.begin(), res.end(), cmp2);
                return res;
            } else {
                vector<Interval> res(intervals.begin(), it);
                vector<Interval>::iterator last =
                    lower_bound(it, intervals.end(), newInterval, cmp);
                if (last == intervals.end()) {
                    res.push_back(
                        Interval(min(it->start, newInterval.start), newInterval.end));
                    sort(res.begin(), res.end(), cmp2);
                    return res;
                } else {
                    if (last->start > newInterval.end)
                        res.push_back(Interval(min(it->start, newInterval.start), newInterval.end)), last--;
                    else 
                    res.push_back(Interval(min(it->start, newInterval.start), 
                        max(last->end, newInterval.end)));
                    while (++last != intervals.end())
                        res.push_back(*last);
                    sort(res.begin(), res.end(), cmp2);
                    return res;
                }
            }
        }
    }
};