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…

leetcode_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) {}
 * };
 */

void find(vector<Interval> &intervals, int val, int& pos, int& in) {
    in = 0;
    for (pos = 0; pos < intervals.size(); ++pos) {
        if (val < intervals[pos].start)
            break;
        else if (val <= intervals[pos].end) {
            in = 1;
            break;
        }
    }
}

class Solution {
public:
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        vector<Interval> ans;
        int st_pos, st_in;
        int end_pos, end_in;
        find(intervals, newInterval.start, st_pos, st_in);
        find(intervals, newInterval.end, end_pos, end_in);
        for (int i = 0; i < st_pos; ++i)
            ans.push_back(intervals[i]);
        if (st_in == 0 && end_in == 0) {
            ans.push_back(newInterval);
        }
        else if (st_in == 0 && end_in == 1) {
            Interval tmp(newInterval.start, intervals[end_pos].end);
            ans.push_back(tmp);
        }
        else if (st_in == 1 && end_in == 0) {
            Interval tmp(intervals[st_pos].start, newInterval.end);
            ans.push_back(tmp);
        }
        else {
            Interval tmp(intervals[st_pos].start, intervals[end_pos].end);
            ans.push_back(tmp);
        }
        for (int i = end_pos + end_in; i < intervals.size(); ++i)
            ans.push_back(intervals[i]);
        return ans;
    }
};