Insert Interval

Insert Interval

Given a non-overlapping interval list which is sorted by start point.

Insert a new interval into it, make sure the list is still in order and non-overlapping (merge intervals if necessary).

Example

Insert [2, 5] into [[1,2], [5,9]], we get [[1,9]].

Insert [3, 4] into [[1,2], [5,9]], we get [[1,2], [3,4], [5,9]].

------------------- thinking ---------------------------

BUGs -> pay attention to the comparison -> bigger or smaller

http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html

------------------- codes -----------------------------

/**

 * Definition of Interval:

 * classs Interval {

 *     int start, end;

 *     Interval(int start, int end) {

 *         this->start = start;

 *         this->end = end;

 *     }

 */

class Solution {

public:

    /**

     * Insert newInterval into intervals.

     * @param intervals: Sorted interval list.

     * @param newInterval: new interval.

     * @return: A new interval list.

     */

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {

        // write your code here

        vector<Interval> result;

        int i = 0;

        while (i < intervals.size()) {

            if (newInterval.start > intervals[i].end) {

                result.push_back(intervals[i]);

            } else if (newInterval.end < intervals[i].start) {

                break;

            } else {

                newInterval.start = newInterval.start<intervals[i].start?newInterval.start:intervals[i].start;

                newInterval.end = newInterval.end>intervals[i].end?newInterval.end:intervals[i].end;

            }

            i++;

        }

        result.push_back(newInterval);

        for (int k = i; k < intervals.size(); k++) {

            result.push_back(intervals[k]);

        }

        return result;

    }

};