Merge Overlapping Intervals II  

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg Cisco eBay Facebook Goldman Sachs Google IXL Microsoft Oracle Palantir Technologies PayPal Qualtrics Salesforce Splunk Twitter Uber VMware Walmart Labs Yahoo Yandex
Array Sorting

Problem Statement  

In the “Merge Overlapping Intervals II” problem we have given a set of intervals. Write a program that will merge the overlapping intervals into one and print all the non-overlapping intervals.

Input Format  

The first line containing an integer n.

Second-line containing n pairs where each pair is denoting the interval.

Output Format  

Print all the non-overlapping intervals in where each interval contains 2 integer values.

Please click Like if you loved this article?

Constraints  

  • 1<=n<=10^5
  • 1<= interval first <= interval second <= 10^9

Example  

4
1 3 2 6 8 10 15 18
1 6 
8 10 
15 18

Algorithm  

First, we sort the vector of the pair on the basis of the first value. Now we insert the first interval into our merged list and continue considering each interval in turn as follows: If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.

A simple proof by contradiction shows that this algorithm always produces the correct answer. First, suppose that the algorithm at some point fails to merge two intervals that should be merged. This would imply that there exists some triple of indices i, j, and k in a list of intervals ints such that i < j < k and (a[i], a[k]) can be merged, but neither (a[i], a[j]) or (a[j], a[k]) can be merged. From this scenario follow several inequalities:

  • a[i].second<a[j].first
  • a[j].second<a[k].first
  • a[i].second≥a[k].first
See also
Maximum weight transformation of a given string

Implementation  

C++ Program

#include <bits/stdc++.h>
using namespace std;

void merge(vector<pair<int,int>> &intervals) 
{
    sort(intervals.begin(), intervals.end());
    vector<pair<int,int>> merged;
    for(auto interval : intervals) 
    {
        if(merged.empty() || merged.back().second < interval.first) {
            merged.push_back({interval});
        }
        else 
        {
            merged.back().second = max(merged.back().second, interval.second);
        }
    }
    for(auto u: merged)
    {
        cout<<u.first<<" "<<u.second<<endl;
    }
}
    
int main()
{
   int n;
   cin>>n;
   vector<pair<int,int>> a;
   for(int i=0;i<n;i++)
   {
       int x,y;
       cin>>x>>y;
       a.push_back({x,y});
   }
   merge(a);
   return 0;
}

Java Program

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
class sum
{
    public static void merge(int[][] intervals) 
    {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList<int[]> merged = new LinkedList<>();
        for (int[] interval : intervals) 
        {
            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) 
            {
                merged.add(interval);
            }
            else 
            {
                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
            }
        }
        merged.toArray(new int[merged.size()][]);
        for(int i=0;i<merged.size();i++)
        {
            System.out.println(merged.get(i)[0]+" "+merged.get(i)[1]);
        }
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[][] = new int [n][2];
        for(int i=0;i<n;i++)
        {
            a[i][0] = sr.nextInt();
            a[i][1] = sr.nextInt();
        }
        merge(a);
    }
}
2
1 4 3 6
1 6

Complexity Analysis  

Time Complexity

O(nlogn) where n is the number of pairs/intervals given to us. Here we performing sorting which leads us to nlogn time complexity.

Space Complexity

O(n) where n is the number of nonoverlapping intervals to store the output.

Please click Like if you loved this article?