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

The solution is very easy. The explanation has been provided in the code as a comment.

/*
* File     : Insert_overlapping_interval.cpp
*/
    

#include<iostream>
#include<string>
#include<vector>

using namespace std;

struct Interval 
{     
  int start;
  int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

static bool compare(Interval a, Interval b) 
{
    return (a.start<b.start);
}
    
vector<Interval> insert_interval(vector<Interval>& intervals, Interval newInterval) 
{
  // simply push the new interval to the old interval
    intervals.push_back(newInterval);
    
    //sort all the intervals 
    sort(intervals.begin(), intervals.end(), compare);

    //vector to store the final result.
    vector<Interval> result;
  
    //insert the first interval
  result.push_back(intervals[0]);
        
  for (auto interval: intervals) 
  {
  // if the end of the current interval is greater than the 
  // beginning of the next interval, then merge it
    if(result.back().end >= interval.start) 
      result.back().end = max(interval.end, result.back().end);
        else
          result.push_back(interval);
    }
        
        return result;
}

int main()
{

    vector<Interval> Intervals; 
    Interval newInterval; 
  
    newInterval.start = 1; 
    newInterval.end = 2; 
    Intervals.push_back(newInterval); 

    newInterval.start = 3; 
    newInterval.end = 5; 
    Intervals.push_back(newInterval); 

    newInterval.start = 6; 
    newInterval.end = 7; 
    Intervals.push_back(newInterval); 

    newInterval.start = 8; 
    newInterval.end = 10; 
    Intervals.push_back(newInterval); 

    newInterval.start = 12; 
    newInterval.end = 16; 
    Intervals.push_back(newInterval); 

    newInterval.start = 4; 
    newInterval.end = 9; 
  
    vector<Interval> ans = 
          insert_interval(Intervals, newInterval); 
  
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i].start << ", "
             << ans[i].end << "\n"; 
  


  return 0;
}