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)