You are given a collection of intervals, merge all overlapping intervals.
Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
This problem can be solved in 2 ways:
- Brute force approach
- By sorting the input array
1. Brute Force approach
In this approach, starting from the first interval, we compare with all the other intervals for overlapping. If we find an overlapping, then we merge those intervals and continue to check with the next elements.
2. By sorting the input array.
First, we sort the input array.
Then we add the first element into the “result_set”. Then if the next interval begins after the previous interval ends, then they don’t overlap each other.
We shall look at the passes by taking the input after the code:
Solution in C++
#include<iostream> #include<vector> using namespace std; struct Interval { int start; int end; }; /*Merge Intervals Using Brute force START */ bool check_is_intersection(Interval &int1, Interval &int2) { if(int1.end<int2.start || int2.end<int1.start) return false; return true; } void mergeIntervalsToFirst(Interval &int1, Interval &int2) { if(int1.start>int2.start) int1.start=int2.start; if(int1.end<int2.end) int1.end=int2.end; } vector<Interval> merge_using_brute_force(vector<Interval> &intervals) { vector<Interval> result_set; if(intervals.size()==0) return result_set; int total_intervals_length = intervals.size(); bool isMerge=false; for(int outer_loop = 0; outer_loop < total_intervals_length; ++outer_loop) { // Insert the first pair into the result set if(outer_loop==0) { result_set.push_back(intervals[0]); } else { // from the second pair, check if there is possibility of overlapping int length_of_result_set = result_set.size(); for(int inner_loop = 0; inner_loop < length_of_result_set; ++inner_loop) { if(check_is_intersection(result_set[inner_loop], intervals[outer_loop])) { // if we found an overlapping element, then merge those two pairs mergeIntervalsToFirst(result_set[inner_loop], intervals[outer_loop]); //Check for remaining intervals pairs to be overlapped inside the result set. vector<Interval>::iterator iter=result_set.begin()+inner_loop+1; while(iter!=result_set.end()) { if(check_is_intersection(result_set[inner_loop], *iter)) { mergeIntervalsToFirst(result_set[inner_loop], *iter); result_set.erase(iter); } else ++iter; } isMerge=true; break; } } // If the present interval[outer_loop] is not merged with any other interval, then it means that it didnt overlap. // Hence Push the interval into the result set. if(!isMerge) { result_set.push_back(intervals[outer_loop]); } else { // reset the value isMerge=false; } } } return result_set; } /*Merge Intervals Using Brute force END */ /*Merge Intervals Using sorting START */ static bool comp(const Interval& a, const Interval& b) { return a.start < b.start; } vector<Interval> merge_using_sort_method(vector<Interval> &intervals) { vector<Interval> result_set; if(intervals.empty()) { return result_set; } sort(intervals.begin(), intervals.end(), comp); result_set.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) { if (result_set.back().end < intervals[i].start) result_set.push_back(intervals[i]); else result_set.back().end = max(result_set.back().end, intervals[i].end); } return result_set; } /*Merge Intervals Using sorting END */ int main() { vector<Interval> itv = { {1,3}, {8,10},{2,6}, {15,18} }; //vector<Interval> result = merge_using_brute_force(itv) ; vector<Interval> result = merge_using_sort_method(itv) ; for (auto &i : result) cout << i.start << ' ' << i.end << endl; }
Output:
1 6 8 10 15 18
Tracing Output using Brute Force Method:
Input Set {1,3}, {8,10}, {2,6}, {15,18} result_set = NULL Pass 1: outer_loop = 0 to 3 Hence add {1, 3} to result set.
result_set = {1, 3} Pass 2: outer_loop = 1 to 3 length_of_result_set = 1 inner_loop = 0 to 1 check_is_intersection(result_set[0], intervals[1]) false enter the interval at intervals[1] into result set.
result_set = {1, 3}, {8,10} Pass 3: outer_loop = 2 to 3 length_of_result_set = 2 inner_loop = 0 to 2 check_is_intersection(result_set[0], intervals[2]) true mergeIntervalsToFirst({1, 3}, {2, 6}) => {1, 6} Check if any other intervals inside the result set is an overlap. while (result_set[1] to 1) check_is_intersection({1, 6}, {8, 10}) false
result_set = {1, 6}, {8,10} Pass 4: outer_loop = 3 to 3 length_of_result_set = 2 inner_loop = 0 to 2 check_is_intersection(result_set[0], intervals[3]) false enter the interval at intervals[3] into result set. Final result ={1, 6}, {8,10}, {15, 18}
Tracing Output using Sort Method
Input Set {1,3}, {8,10}, {2,6}, {15,18} First step is to sort all the intervals. After sorting, below will be the intervals. Input Set {1,3}, {2,6}, {8,10}, {15,18} Add the first interval to result set result_set = {1, 3}
result_set = {1, 3} Pass 1: for 1 to 3 if (result_set.back().end < intervals[i].start) => (3 < 2) false, Hence merge Hence result_set.back().end = max(result_set.back().end, intervals[i].end); = max(3, 6) = 6
result_set = {1, 6} Pass 2: for 2 to 3 if (result_set.back().end < intervals[i].start) => (6 < 8) true, add {8, 10} to reslut set
result_set = {1, 6}, {8, 10} Pass 3: for 3 to 3 if (result_set.back().end < intervals[i].start) => (8 < 18) true, add {15, 18} to reslut set Final result ={1, 6}, {8,10}, {15, 18}
Please write your answers in the comment section of this post.