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