Recent Posts

Merge Intervals

Written by

studymite

Problem

Given an array of intervals merge all overlapping intervals.

Input : [[1,3],[2,6],[8,10],[15,18]]

Output : [[1,6],[8,10],[15,18]]

Brute Force Approach

Sort the intervals array and run a nested loop to find all merge intervals.

Optimal Approach

 

#include <bits/stdc++.h>
using namespace std;

void printOverlappingIntervals(vector<vector<int>> intervals){
if(intervals.size() < 2) return;


vector&lt;vector&lt;int&gt;&gt; mergedIntervals;
mergedIntervals.push_back(intervals[0]);

for(int i = 1; i &lt; intervals.size(); i++){
	vector&lt;int&gt; &amp;last = mergedIntervals.back();
    if(last[1] &gt;= intervals[i][0]){
      last[1] = max(last[1], intervals[i][1]);
    } else {
      mergedIntervals.push_back(intervals[i]);
    }
}

for(auto i:mergedIntervals){
	cout&lt;&lt;"[";
  	for(auto j:i){
    	cout&lt;&lt;j&lt;&lt;" ";
    }
  	cout&lt;&lt;"]";
}



}


int main() {
vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
sort(intervals.begin(), intervals.end());
printOverlappingIntervals(intervals);
return 0;
}

TC – O(NlogN) // for sorting and linear traversal

SC – O(N)

Merge Intervals