57. Insert Interval

Description

Given a set ofnon-overlappingintervals, 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].

Discussion

Method

Easier to split into 3 sub function:

1. insertNewInterval

2. skip current interval of the list

3. push current interval of the list

/**
 * 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>& intervals, Interval newInterval) {
        vector<Interval> rst;
        bool inserted = false;
        for(int loop = 0; loop < intervals.size(); ++loop) {
            if(inserted == false && true == toInsert(intervals[loop], newInterval)) {
                rst.push_back(newInterval);
                inserted = true;
            }
            if(true == toSkip(intervals[loop], newInterval)) {
                continue;
            }
            if(true == toPush(intervals[loop], newInterval)) {
                rst.push_back(intervals[loop]);
            }
        }

        if(false == inserted) {
            rst.push_back(newInterval);
        }
        return rst;
    }

private:
    bool toInsert(Interval &interval, Interval &newInterval) {
        bool rst = false;
        if(interval.start > newInterval.end)
            rst = true;
        return rst;
    }

    bool toPush(Interval &interval, Interval &newInterval) {
        bool rst = false;
        if(interval.end < newInterval.start || interval.start > newInterval.end) {
            rst = true;
        }
        return rst;
    }

    bool toSkip(Interval &interval, Interval &newInterval) {
        bool rst = false;
        if((interval.start >= newInterval.start && interval.end <= newInterval.end) || 
           (interval.start <= newInterval.start && interval.end >= newInterval.end) ||
           (interval.start >= newInterval.start && interval.start <= newInterval.end) ||
           (interval.end >= newInterval.start && interval.end <= newInterval.end)) {
            newInterval.start = min(newInterval.start, interval.start);
            newInterval.end = max(newInterval.end, interval.end);
            rst = true;
        }
        return rst;
    }
};