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].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
This problem can be solved in 2 ways:
1. Brute force approach
2. 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.
In this approach we take 2 loops.
Outer loop is for iterating the given “interval set”. Inner loop is to iterate the “result set”.
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.
If the next interval begins before the previous interval ends, then they overlap each other and should be merged with each other.
We shall look at the passes by taking the input after the code:
Solution in C++
/*
* File : Merge_Intervals.cpp
* Author : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/
#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;
}
Brute force approach analysis
Let us take the below input:
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}
=================Sorting 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}
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}