Insert Interval

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

Constraints:

• 0 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= intervals[i][0] <= intervals[i][1] <= 105

• intervals is sorted by intervals[i][0] in ascending order.

• newInterval.length == 2

• 0 <= newInterval[0] <= newInterval[1] <= 105

Solutions

🧠 Cpp

class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        //input check
        if(intervals.empty())
            return {newInterval};

        vector<vector<int>> res;
        res.reserve(intervals.size() + 1);
        int a = newInterval[0], b = newInterval[1]; 

        //find interval that could be altered to contain newInterval
        auto iter = begin(intervals),
                    iter_end = end(intervals);
        for(;iter < iter_end; ++iter)
        {
            int &x1 = iter->at(0), &x2 = iter->at(1);

            //booster to find correct element
            if(a > x1 && a > x2 && next(iter) != iter_end)
            {
                res.emplace_back(*iter);
                continue;
            }
            break;
        }

        //return {*iter};
        //alter this interval or insert new before interval it
        {
            int &x1 = iter->at(0), &x2 = iter->at(1);

            //(x1,a,b,x2) fully included
            if( x1 <= a && b <= x2 )
                return intervals;
            //(a,x1,x2,b) fully included
            if( a <= x1 && x2 <= b )
            {
                *iter = newInterval;
            }
            else if( a == x2 )
            {
                x2 = b;
            }
            //(a,x1,b,x2)
            else if( a < x1  && x1 <= b )
            {
                x1 = a;
            }
            //(x1,a,x2,b)
            else if( a <= x2 && x2 < b)
            {
                x2 = b;
            }
            //(a,b,x1,x2) //we can insert a new interval right before iter
            else if(x1 >= b)
            {
                iter = intervals.insert(iter, newInterval);//insert whole interval at prev pos
            }
            else if(next(iter) == iter_end)
            {
                if(a <= x2)
                    x2 = b;
                else
                {
                    res.emplace_back(*iter);
                    iter = intervals.insert(iter_end, newInterval);
                }
            }

        }

        //return {*iter};


        //check that intervals after modified/inserted one are not overlaping
        a = iter->at(0), b = iter->at(1);
        iter_end = end(intervals);
        auto finish_iter = next(iter);

        if(finish_iter != iter_end)
        for(;next(finish_iter) != iter_end; finish_iter++)
        {
            int &x1 = finish_iter->at(0), &x2 = finish_iter->at(1);
            if(b == x1 ||  b <= x2)
            {
                break;
            }
            if( b < next(finish_iter)->at(0))   
            {
                break;
            }
        }

        //take right valur from last overlapping
        if(finish_iter != iter_end)
        {
            int &x1 = finish_iter->at(0), &x2 = finish_iter->at(1);
            if(b >= x1)
            {
                if(x2 > b)
                    iter->at(1) = x2;
                finish_iter++;
            }
        }

        //at this point we finished with our interval,
        //all other intervals after it is not overlapping
        res.emplace_back(*iter);
        for(;finish_iter != iter_end; finish_iter++)
            res.emplace_back(*finish_iter);


        return res;
    }
};