How to Merge Overlapping Intervals in C ++

In this article, we are going to learn how to Merge Overlapping Intervals in C++. In these types of problems, we will be given an array of intervals and we have to find whether the overlap or not.

There are various approaches to solve this problem. However there time complexity and space complexity differs. Here we will discuss the most efficient approach of O (N log N) time complexity and O(1) space complexity.

The C++ program to merge overlapping intervals

Below is our code:

#include<bits/stdc++.h>  
using namespace std;  
  
struct Interval  
{  
    int start, end;  
};  
   
bool compare(Interval i1, Interval i2)  
{ return i1.start < i2.start; }  
  
void merge(vector<Interval> A, int n)  
{  
    sort(A.begin(), A.end(), compare);  
    int index = 0;
    for (int i=1; i<n; i++)  
    {  
        if (A[index].end >=  A[i].start)  
        {   
            A[index].end = max(A[index].end, A[i].end);  
            A[index].start = min(A[index].start, A[i].start);  
        }  
        else { 
            A[index] = A[i];  
            index++; 
        }     
    }  
    A.erase(A.begin()+index+1,A.end());
    cout << "\nMerged Intervals are: ";  
    for (int i = 0; i <= index; i++)  
        cout << "[" << A[i].start << ", " << A[i].end << "] ";  
}  
  
int main()  
{  
    vector<Interval> A = { {3,4}, {5,9}, {2,4} };  
    int n = sizeof(A)/sizeof(A[0]);  
    merge(A, n);  
    return 0;  
}

Output:-

Merged Intervals are: [5, 9] [3, 4]

In this code, we initialize array A and then we will call void merge(Interval A[], int n) function. After that we will sort the array. Once the array is sorted we will have intervals with there first value sorted in ascending order. Then we will write a simple algorithm to overlap the merging intervals using for a loop as shown in code. So now we have an array of size ‘n’ which we will change to the new size using erase() function in the STL library. In last, we will print our output on screen using cout.

This is the best approach to solve this type of problem. There are other approaches also which are less efficient than this. The time complexity for this code is O(NlogN) and space complexity O(1).

Thank you!

Also, read: Password Validation Program in C++

Leave a Reply

Your email address will not be published. Required fields are marked *