# Merge Intervals

Written By -

## 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<vector<int>> mergedIntervals;
mergedIntervals.push_back(intervals[0]);

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

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

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)

Related Posts:

Online Compilers