RUN

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)

Report Error/ Suggestion

Related Posts:




CopyRight © 2020

CopyRight © 2020