35. 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:

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

Example 3:

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4:

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

Example 5:

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Solution:

Insert and Merge

class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {

        int i = 0;

        while (i < intervals.size())
        {
            if (intervals[i][0] >= newInterval[0])
            {
                break;
            }
            i++;
        }

        intervals.insert(intervals.begin() + i, newInterval);

        vector<vector<int>> res;
        int idx = 0;

        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] <= intervals[idx][1])
            {
                intervals[idx][0] = min(intervals[i][0], intervals[idx][0]);
                intervals[idx][1] = max(intervals[i][1], intervals[idx][1]);
            }
            else
            {
                res.push_back({intervals[idx][0], intervals[idx][1]});
                idx = i;
            }
        }

        res.push_back({intervals[idx][0], intervals[idx][1]});

        return res;
    }
};

Time Complexity: O(n)