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

Difficulty
Hard

Related Problems
[LeetCode 56] Merge Intervals

Analysis

This is similar to the problem Merge Intervals except that the intervals are sorted already.
We just need to find the index that we will insert the interval into, or merge it if over-lapped.

The index we insert the interval into will have two cases:

• 1. The interval to insert is not overlapped with the existing intervals. this is easy, we just insert it.
• 1. The interval to insert is overlapped with the existing intervals, it may even be overlapped with multiple intervals. In this case, we need to update the new interval.

Demo

Iterate over the given intervals, if interval[i].end < newInterval.start, put it into a container, else, merge interval[i] with newInterval to get a newInterval, before we push it into the container, continue iterating the remaining intervals, and repeat the previous process.

1. Cpp solution

class Solution {
public:
    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> result;
        int n = intervals.size();
        int i = 0;
        for(; i < n && intervals[i].end < newInterval.start; ++i){
            result.push_back(intervals[i]);
        }
        if(i == n){
            result.push_back(newInterval);
            return result;
        }

        newInterval.start = min(intervals[i].start, newInterval.start);
        for(; i < n && intervals[i].start <= newInterval.end; ++i){
            newInterval.end = max(intervals[i].end, newInterval.end);
        }
        result.push_back(newInterval);
        for(; i < n; ++i){
            result.push_back(intervals[i]);
        }
        return result;
    }
};

2. Go solution

func insert(intervals []Interval, newInterval Interval) []Interval {
    res := []Interval{}
    n := len(intervals)
    if n == 0 {
        res = append(res, newInterval)
        return res
    }

    i := 0
    for ; i < n && intervals[i].End < newInterval.Start; i++ {
        res = append(res, intervals[i])
    }

    if i == n {
        res = append(res, newInterval)
        return res
    }

    newInterval.Start = min(newInterval.Start, intervals[i].Start)
    // update newInterval's End
    for ; i < n && intervals[i].Start <= newInterval.End; i++ {
        newInterval.End = max(newInterval.End, intervals[i].End)
    }

    res = append(res, newInterval)
    for ; i < n; i++ {
        res = append(res, intervals[i])
    }

    return res
}

func max(a, b int) int {
    return int(math.Max(float64(a), float64(b)))
}

func min(a, b int) int {
    return int(math.Min(float64(a), float64(b)))
}

Reference