TutorialStudyMite
Merge Intervals
Sstudymite1 min read
Beginner friendly
Track completion, mastery, and revision.
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;
}
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)
Finished reading?