LeetCode: 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].

---

We can simply add the newInterval into the intervals vector and then call the function mergeIntervals in the previous problem. Or we can sort the intervals first and merging the intervals while traversing the vector.

C++ Code:

/*
 * func: insert_interval
 * goal: insert an interval into a list and merge them if necessary
 * @param intervals: orignal non-overlapping intervals
 * @param newInterval: interval going to be inserted
 * return: rearranged intervals
 */
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval){
    intervals.emplace_back(newInterval);
    return merge_interval(intervals);

}

Python Code:

# func: Insert a interval into a list of intervals and merge if necessary
# @param intervals: a list of intervals
# @param newInterval: interval to be inserted
# @return: new interval list
def insert_interval(intervals, newInterval):
    result = []
    i = 0
    #Adding intervals non-overlapping with the new one
    while i < len(intervals) and intervals[i].end < newInterval.start:
        result.append(intervals[i])
        i += 1
    #Adding intervals overlapping with the new one
    while i < len(intervals) and newInterval.end >= intervals[i].start:
        newInterval.start = min(intervals[i].start, newInterval.start)
        newInterval.end = max(intervals[i].end, newInterval.end)
        i += 1
    result.append(newInterval)

    while i < len(intervals) and intervals[i].start > newInterval.end:
        result.append(intervals[i])
        i += 1
    return result