Merge Overlapping Intervals II

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.

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

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.