ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Given an array of non overlapping integers, insert a new interval by merging them, solution in C++

prodevelopertutorial October 17, 2018

Given an array of sorted intervals of  non overlapping integers, insert a new interval into intervals by merging them

 

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

 

Solution in C++

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

Output:

1, 2
3, 10
12, 16

 

 

Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io