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