Merge Overlapping Intervals

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Cisco eBay Facebook Goldman Sachs Google IXL Microsoft Oracle Palantir Technologies PayPal Splunk Square Twitter Uber VMware Yandex
Array SortingViews 2322

In merge overlapping intervals problem we have given a collection of intervals, merge and return all overlapping intervals.

Example

Input : [[2, 3], [3, 4], [5, 7]]

Output: [[2, 4], [5, 7]]

Explanation:

We can merge [2, 3] and [3, 4] together to form [2, 4]

Merge Overlapping Intervals

Approach for finding Merge Overlapping Intervals

The idea here is to sort the intervals based on the starting index so that we can merge them just by keeping a track of the start and end index for every merged interval.

If we have a merged interval [a, b] and the next interval is [c, d]. So there are three cases:

  • When c<=d and d>=b then the resultant interval would be [a, d]

 

  • And when c<=d and d<=b then the resultant interval would be [a, b]

  • When c>d, then the intervals can not be merged and we will have two resultant intervals [a, b] and [c, d]

Algorithm for finding Merge Overlapping Intervals

Step 1: Sort the intervals first based on their starting index and then based on their ending index. This step will take (nlogn) time.

Step 2: Initialize the starting and ending variable as -1, this indicates that currently there is no interval picked up.

Step 3: Iterate over the interval array and check these three conditions:

  1. If the starting and ending variable is -1, then pick the ith interval and update the starting and ending variable.
  2. Now check If the ith interval overlaps with the previously picked interval then modify the ending variable with the maximum of the previous ending and the end of the ith interval.
  3. If the ith interval does not overlap with the previously picked interval then push the previous interval in the ans array and update the starting and ending variable with the ith interval.

Implementation

C++ program Merge Overlapping Intervals

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end());
    vector<vector<int>> ans;
    int i=0;
    int n=intervals.size(),s=-1,e=-1;
    while(i<n){
        if(s==-1){
            s=intervals[i][0];
            e=intervals[i][1];
            i++;
        }
        else{
            if(intervals[i][0]<=e){
                e=max(e,intervals[i][1]);
                i++;
            }
            else{
                ans.push_back(vector<int>{s, e});
                s=intervals[i][0];
                e=intervals[i][1];
                i++;
            }
        }
    }
    if(s!=-1){
        ans.push_back(vector<int>{s, e});
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector<vector<int>> intervals(n);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        intervals[i].push_back(a);
        intervals[i].push_back(b);
    }
    vector<vector<int>> ans = merge(intervals);
    cout<<"Intervals after merge operation are:\n";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
    }
}
4
1 3
2 6
8 10
15 18
Intervals after merge operation are:
1 6
8 10
15 18

JAVA program for Merge Overlapping Intervals

import java.util.*;
public class Main
{
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a,b)->Integer.compare(a[0],b[0]));
        ArrayList<int[]> list = new ArrayList();
        int i=0;
        int n=intervals.length,s=-1,e=-1;
        while(i<n){
            if(s==-1){
                s=intervals[i][0];
                e=intervals[i][1];
                i++;
            }
            else{
                if(intervals[i][0]<=e){
                    e=Math.max(e,intervals[i][1]);
                    i++;
                }
                else{
                    list.add(new int[]{s, e});
                    s=intervals[i][0];
                    e=intervals[i][1];
                    i++;
                }
            }
        }
        if(s!=-1){
            list.add(new int[]{s, e});
        }
        int[][] arr = new int[list.size()][2];
		return list.toArray(arr);
    }
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int n = sc.nextInt();
	    int[][] arr = new int[n][2];
	    for(int i=0;i<n;i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        int[][] ans = merge(arr);
		System.out.println("Intervals after merge operation are:");
		for(int i=0;i<ans.length;i++){
		    System.out.println(ans[i][0]+" "+ans[i][1]);
		}
	}
}
5
1 2
2 5
2 6
7 9
15 18
Intervals after merge operation are: 
1 6 
7 9 
15 18

Complexity Analysis

Time Complexity

O(nlogn)

Sorting takes O(nlogn) time and traversal of the array for once takes O(n) time.

Hence to total time complexity is O(nlogn + n) i.e., O(nlogn)

Space Complexity

O(n) because we use a vector to store the result and its maximum size is N when all the intervals are overlapped.

References

Translate ยป