Merge Overlapping Intervals

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

  1. If the current interval does not overlap with the stack top, push it
  2. 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;
}
Try It

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

  1. 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.
  2. 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;
}
Try It

 


Next > < Prev
Scroll to Top