Problem Statement: You are given an array of non-overlapping intervals where intervals[i] = [start, end] represent the start and the end of the ith interval, and intervals is sorted in ascending order by start. 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 are still sorted in ascending order by start and intervals still do not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion. 

Examples:

Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] 
Output: [[1,5],[6,9]] 
Explanation: Intervals 1,3 and 2,5 can be merged to make 1,5. 

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

Solution 

Disclaimer: Don’t jump directly to the solution, try it out yourself first. 

Approach: We will keep track of start and end points in the given array and add new intervals based on the start and end of given current intervals. For ex – a=[1,3],[6,9] newInterval=[2,5] 

We start by checking if the new interval can be inserted at that particular position. We can know if the end of the new interval to be inserted is less than the start of the interval in the array. Since 3 is not less than 2, the interval is not inserted. 

Now , we check if the interval in array is before the newInterval , i.e, a[i][1]<newInterval[0]. If the end of the current interval is before the start of the new interval, we know that is a completely separate interval and we can add it to the array. 

Like in this example, we can see 4 ends before 6 starts, so there is no way we can merge them. So,1,4  can be inserted into the result. 

However, in our case 3 is not less than 2. So intervals can be merged. 

Now that we know intervals can be merged, we take the minimum of start points of current interval and newInterval as well as the max of endpoints of current interval and newInterval. 

Here, 2 and 3 get combined, to form a new interval 1-5. 

At, next iteration , now that newInterval[1] < interval[i][0] 5<6 ,i.e, end of new is less than start of  current, we insert 1,5 to result . Then we add all rest of the intervals to the result and return. We do this rather than checking ahead because as soon as a new interval has been inserted, we can replicate the rest of the intervals. 

Result = {[1,5],[6,9]} 

Example:

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 

First we check , newInterval[1] < interval[i][0] , 8<1,which is not true. Now we check interval[i][1] < newInterval[0] , i.e , if current ending is less than new start , we  can then add current to result. 

At iteration 2, 

First we check , newInterval[1] < interval[i][0] , 8<3,which is not true. Now we check interval[i][1] < newInterval[0] , i.e , 5<4 , not true. That means we can merge, newInterval now becomes 3,8 

At iteration 3, 

First we check , newInterval[1] < interval[i][0] , 8<6,which is not true. Now we check interval[i][1] < newInterval[0] , i.e , 7<3 , not true. That means we can merge, newInterval now becomes 3,8.

At iteration 4,

First we check , newInterval[1] < interval[i][0] , 8<8,which is not true. Now we check interval[i][1] < newInterval[0] , i.e , 10<3 , not true. That means we can merge, newInterval now becomes 3,10 

At iteration 5,

First we check , newInterval[1] < interval[i][0] , 10<12,which is true. So we add 3,10 to the result.  Then we copy the rest of the intervals to the result and return. 

Note: we add newIntervals at the end after the whole loop is run, in case the last Interval in intervals got merged and was never added to the answer.

Code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> insert(vector<vector<int>>& a, vector<int>& ni) {
int n = a.size();
vector<vector<int>> ans;
for(int i = 0;i<n;i++)
{
if(ni[1]<a[i][0]) //if interval to be merged is less than interval in array
{
ans.push_back(ni);
for(;i<n;i++)
{
ans.push_back(a[i]);
}
return ans;
}
else if(a[i][1] < ni[0]) //If current interval is before newInterval
ans.push_back(a[i]);
else
{
ni[0] = min(ni[0],a[i][0]);
ni[1] = max(ni[1],a[i][1]);
}
}
ans.push_back(ni);
return ans;
}

int main(){
vector<vector<int>>intervals;
intervals.push_back({1,3});
intervals.push_back({6,9});
vector<int>newInterval;
newInterval.push_back(2);
newInterval.push_back(5);
intervals = insert(intervals,newInterval);
for(int i=0;i<intervals.size();i++){
cout<<"["<<intervals[i][0]<<","<<intervals[i][1]<<"]"<<" ";
}
return 0;
}

Special thanks to Rishika Gupta for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article