# 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)