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; }