57. Insert Interval • Algorithm Solutions

1. Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [$start_i$, $end_i$] represent the start and the end of the $i^{th}$ interval and intervals is sorted in ascending order by $start_i$. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by $start_i$ and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don’t need to modify intervals in-place. You can make a new array and return it.

2. Example

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

3. Constraints

0 <= intervals.length <= 10$^{4}$
intervals[i].length == 2
0 <= $start_i$ <= $end_i$ <= 10$^{5}$
intervals is sorted by $start_i$ in ascending order.
newInterval.length == 2
0 <= start <= end <= 10$^{5}$

4. Solutions

Array

n = intervals.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    vector<vector<int>> insert(const vector<vector<int>> &intervals, vector<int> interval) {
        const int n = intervals.size();
        vector<vector<int>> merged_intervals;
        merged_intervals.reserve(n + 1);

        int i = 0;

        while (i < n && intervals[i][1] < interval[0]) {
            merged_intervals.push_back(intervals[i]);
            ++i;
        }

        while (i < n && intervals[i][0] <= interval[1]) {
            interval[0] = min(interval[0], intervals[i][0]);
            interval[1] = max(interval[1], intervals[i][1]);
            ++i;
        }

        merged_intervals.push_back(interval);

        while (i < n) {
            merged_intervals.push_back(intervals[i]);
            ++i;
        }

        return merged_intervals;
    }
};

Binary Search

n = intervals.size()
Time complexity: O(n)
Space complexity: O(1)

// Binary search does not improve overall time complexity and it is still O(n).
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>> intervals, vector<int> newInterval) {
        auto left_iter = lower_bound(
            intervals.begin(),
            intervals.end(),
            newInterval[0],
            [](const vector<int> &interval, const int value) { return interval[0] < value; });

        auto right_iter = left_iter;
        while (left_iter != intervals.begin() && (left_iter - 1)->back() >= newInterval[0]) {
            --left_iter;
            newInterval[0] = left_iter->front();
            newInterval[1] = max(left_iter->back(), newInterval[1]);
        }

        while (right_iter != intervals.end() && right_iter->front() <= newInterval[1]) {
            newInterval[1] = max(right_iter->back(), newInterval[1]);
            ++right_iter;
        }

        auto iter = intervals.erase(left_iter, right_iter);
        intervals.insert(iter, newInterval);

        return intervals;
    }
};