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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 class Solution {

public:

    vector<vector<int>> insert(vector<vector<int>>& in, vector<int>& ne) {

        vector<vector<int>> res;

        int i=0;

        int n=in.size();

        if(n==0)

        {

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

            return res;

        }

        while(i<n&&ne[0]>in[i][1]&&ne[0]>in[i][1])

        {

            res.push_back({in[i][0],in[i][1]});

            ++i;

        }

        int j=i;

      if(j==n)

        {

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

        }

         while(j<n&&ne[1]>=in[j][0])

             ++j;

        if((i==0&&j==0))

        {

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

        while(j<n)

        {

            res.push_back({in[j][0],in[j][1]});

            ++j;

        }

            return res;  

        }

              --j;

        if(j<n&&i<n)

            res.push_back({min(ne[0],in[i][0]),max(ne[1],in[j][1])});

            ++j;

        while(j<n)

        {

            res.push_back({in[j][0],in[j][1]});

            ++j;

        }

        return res;

    }

};