Given a set of intervals, this function will merge the overlapping intervals into one and prints all the non overlapping intervals
Example
INPUT:
arr[] = {{1,6},{3,9},{11,13},{2,5}}
OUTPUT:
After merging the intervals are [1,9], [11,13]
Time Complexity: O(nlogn)
Space Complexity: O(n)
Algorithm
1. Sort the Intervals based on the increasing order of start time
2. Push the first interval on to a stack
3. For each Interval
- If the current interval does not overlap with the stack top, push it
- If the current element overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval
4. Now, Stack conatins merged intervals
C++ Program
#include<bits/stdc++.h>
using namespace std;
// An interval has start time and end time
struct Interval
{
int start, end;
};
// To compare two intervals accoridng to their start time
bool myComp(Interval interval1, Interval interval2)
{
return (interval1.start < interval2.start);
}
// This function takes a set of intervals, merges
// overlapping intervals and prints the result
void mergeIntervals(Interval arr[], int n)
{
// Test if the given set has at least one interval
if (n <= 0)
return;
// Create an empty stack of intervals
stack<Interval> s;
// sorting the intervals in increasing order of start time
sort(arr, arr+n, myComp);
// push the first interval to stack
s.push(arr[0]);
// Start from the next interval and merge if necessary
for (int i = 1 ; i < n; i++)
{
// get interval from stack top
Interval top = s.top();
// if current interval is not overlapping with stack top,
// push it to the stack
if (top.end < arr[i].start)
s.push(arr[i]);
// Otherwise update the ending time of top if ending of current
// interval is more
else if (top.end < arr[i].end)
{
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
// Print contents of stack
cout << "\n After merging Intervals are: ";
while (!s.empty())
{
Interval t = s.top();
cout << "[" << t.start << "," << t.end << "] ";
s.pop();
}
return;
}
int main()
{
Interval arr[]= {{1,6},{3,9},{11,13},{2,5}}; //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
mergeIntervals(arr,n);
return 0;
}Time Complexity: O(nlogn)
Space Complexity: O(1)
Algorithm
1. Sort the intervals based on decreasing order of start time
2. For each Interval, starting from the first interval
- If the current interval is not the first interval and it overlaps with the previous interval, then merge it with previous interval. Keep doing it while the interval overlaps with the previous one.
- Else, add current interval to output list of intervals
C++ Program
#include<bits/stdc++.h>
using namespace std;
// An Interval
struct Interval
{
int start, end;
};
// To compare two intervals accoridng to their start time
bool mycomp(Interval interval1, Interval interval2)
{ return interval1.start > interval2.start; }
void mergeIntervals(Interval arr[], int n)
{
// Sort Intervals in decreasing order of start time
sort(arr, arr+n, mycomp);
// Stores index of last element in the output array
int index = 0;
// Traverse all input Intervals
for (int i=0; i<n; i++)
{
// If this is not first Interval and overlaps
// with the previous one
if (index != 0 && arr[index-1].start <= arr[i].end)
{
while (index != 0 && arr[index-1].start <= arr[i].end)
{
// Merge previous and current Intervals
arr[index-1].end = max(arr[index-1].end, arr[i].end);
arr[index-1].start = min(arr[index-1].start, arr[i].start);
index--;
}
}
// Doesn't overlap with previous, add to the solution
else
arr[index] = arr[i];
index++;
}
// Now arr[0..index-1] stores the merged Intervals
cout << "\n After Merging the Intervals are: ";
for (int i = 0; i < index; i++)
cout << "[" << arr[i].start << ", " << arr[i].end << "] ";
}
// Driver program
int main()
{
Interval arr[] = {{1,6},{3,9},{11,13},{2,5}};
int n = sizeof(arr)/sizeof(arr[0]);
mergeIntervals(arr, n);
return 0;
}
