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> new_interval) {
        vector<vector<int>> merged_intervals;
        merged_intervals.reserve(intervals.size() + 1);

        bool inserted = false;
        for (int i = 0, n = intervals.size(); i < n; ++i) {
            if (intervals[i].back() < new_interval.front()) {
                merged_intervals.push_back(intervals[i]);
            } else if (intervals[i].front() <= new_interval.back()) {
                new_interval.front() = min(intervals[i].front(), new_interval.front());
                new_interval.back() = max(intervals[i].back(), new_interval.back());
            } else {
                merged_intervals.push_back(new_interval);
                inserted = true;

                for (int j = i; j < n; ++j) {
                    merged_intervals.push_back(intervals[j]);
                }

                break;
            }
        }

        if (!inserted) {
            merged_intervals.push_back(new_interval);
        }

        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;
    }
};