Find a pair of overlapping intervals from a given Set

0 0 8 minutes read

Given a 2D array arr[][] with each row of the form {l, r}, the task is to find a pair (i, j) such that the i^th interval lies within the j^th interval. If multiple solutions exist, then print anyone of them. Otherwise, print -1.

Examples:

Input: N = 5, arr[][] = { { 1, 5 }, { 2, 10 }, { 3, 10}, {2, 2}, {2, 15}}
Output: 3 0
Explanation: [2, 2] lies inside [1, 5].

Input: N = 4, arr[][] = { { 2, 10 }, { 1, 9 }, { 1, 8 }, { 1, 7 } }
Output: -1
Explanation: No such pair of intervals exist.

Native Approach: The simplest approach to solve this problem is to generate all possible pairs of the array. For every pair (i, j), check if the i^th interval lies within the j^th interval or not. If found to be true, then print the pairs. Otherwise, print -1.
Time Complexity: O(N²)
Auxiliary Space:O(1)

Efficient Approach: The idea is to sort the segments firstly by their left border in increasing order and in case of equal left borders, sort them by their right borders in decreasing order. Then, just find the intersecting intervals by keeping track of the maximum right border.

Follow the steps below to solve the problem:

Sort the given array of intervals according to their left border and if any two left borders are equal, sort them with their right border in decreasing order.
Now, traverse from left to right, keep the maximum right border of processed segments and compare it to the current segment.
If the segments are overlapping, print their indices.
Otherwise, after traversing, if no overlapping segments are found, print -1.

Below is the implementation of the above approach:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a pair(i, j) such that
// i-th interval lies within the j-th interval
void findOverlapSegement(int N, int a[], int b[])
{
 
    // Store interval and index of the interval
    // in the form of { {l, r}, index }
    vector<pair<pair<int, int>, int> > tup;
 
    // Traverse the array, arr[][]
    for (int i = 0; i < N; i++) {
 
        int x, y;
 
        // Stores l-value of
        // the interval
        x = a[i];
 
        // Stores r-value of
        // the interval
        y = b[i];
 
        // Push current interval and index into tup
        tup.push_back(pair<pair<int, int>, int>(
            pair<int, int>(x, y), i));
    }
 
    // Sort the vector based on l-value
    // of the intervals
    sort(tup.begin(), tup.end());
 
    // Stores r-value of current interval
    int curr = tup[0].first.second;
 
    // Stores index of current interval
    int currPos = tup[0].second;
 
    // Traverse the vector, tup[]
    for (int i = 1; i < N; i++) {
 
        // Stores l-value of previous interval
        int Q = tup[i - 1].first.first;
 
        // Stores l-value of current interval
        int R = tup[i].first.first;
 
        // If Q and R are equal
        if (Q == R) {
 
            // Print the index of interval
            if (tup[i - 1].first.second
                < tup[i].first.second)
                cout << tup[i - 1].second << ' '
                     << tup[i].second;
 
            else
                cout << tup[i].second << ' '
                     << tup[i - 1].second;
 
            return;
        }
 
        // Stores r-value of current interval
        int T = tup[i].first.second;
 
        // If T is less than or equal to curr
        if (T <= curr) {
            cout << tup[i].second << ' ' << currPos;
            return;
        }
        else {
 
            // Update curr
            curr = T;
 
            // Update currPos
            currPos = tup[i].second;
        }
    }
 
    // If such intervals found
    cout << "-1 -1";
}
 
// Driver Code
int main()
{
 
    // Given l-value of segments
    int a[] = { 1, 2, 3, 2, 2 };
 
    // Given r-value of segments
    int b[] = { 5, 10, 10, 2, 15 };
 
    // Given size
    int N = sizeof(a) / sizeof(int);
 
    // Function Call
    findOverlapSegement(N, a, b);
}

Java

// Java program to implement 
// the above approach 
import java.util.*;
import java.lang.*;
 
class pair{
  int l,r,index;
 
  pair(int l, int r, int index){
    this.l = l;
    this.r = r;
    this.index=index;
  }
}
class GFG {
 
  // Function to find a pair(i, j) such that 
  // i-th interval lies within the j-th interval 
  static void findOverlapSegement(int N, int[] a, int[] b) 
  { 
 
    // Store interval and index of the interval 
    // in the form of { {l, r}, index } 
    ArrayList<pair> tup = new ArrayList<>();
 
    // Traverse the array, arr[][] 
    for (int i = 0; i < N; i++) { 
 
      int x, y; 
 
      // Stores l-value of 
      // the interval 
      x = a[i]; 
 
      // Stores r-value of 
      // the interval 
      y = b[i]; 
 
      // Push current interval and index into tup 
      tup.add(new pair(x, y, i)); 
    } 
 
    // Sort the vector based on l-value 
    // of the intervals 
    Collections.sort(tup,(aa,bb)->(aa.l!=bb.l)?aa.l-bb.l:aa.r-bb.r); 
 
    // Stores r-value of current interval 
    int curr = tup.get(0).r; 
 
    // Stores index of current interval 
    int currPos = tup.get(0).index; 
 
    // Traverse the vector, tup[] 
    for (int i = 1; i < N; i++) { 
 
      // Stores l-value of previous interval 
      int Q = tup.get(i - 1).l; 
 
      // Stores l-value of current interval 
      int R = tup.get(i).l; 
 
      // If Q and R are equal 
      if (Q == R) { 
 
        // Print the index of interval 
        if (tup.get(i - 1).r < tup.get(i).r) 
          System.out.print(tup.get(i - 1).index + " " + tup.get(i).index); 
 
        else
          System.out.print(tup.get(i).index + " " + tup.get(i - 1).index); 
 
        return; 
      } 
 
      // Stores r-value of current interval 
      int T = tup.get(i).r; 
 
      // If T is less than or equal to curr 
      if (T <= curr) { 
        System.out.print(tup.get(i).index + " " + currPos); 
        return; 
      } 
      else { 
 
        // Update curr 
        curr = T; 
 
        // Update currPos 
        currPos = tup.get(i).index; 
      } 
    } 
 
    // If such intervals found 
    System.out.print("-1 -1"); 
  }     
 
  // Driver code
  public static void main (String[] args)
  {
 
    // Given l-value of segments 
    int[] a = { 1, 2, 3, 2, 2 }; 
 
    // Given r-value of segments 
    int[] b = { 5, 10, 10, 2, 15 }; 
 
    // Given size 
    int N = a.length; 
 
    // Function Call 
    findOverlapSegement(N, a, b); 
  }
}
 
// This code is contributed by offbeat.

Python3

# Python3 program to implement 
# the above approach
 
# Function to find a pair(i, j) such that
# i-th interval lies within the j-th interval
def findOverlapSegement(N, a, b) :
     
    # Store interval and index of the interval
    # in the form of { {l, r}, index }
    tup = []
     
    # Traverse the array, arr[][]
    for i in range(N) :
         
        # Stores l-value of
        # the interval
        x = a[i]
         
        # Stores r-value of
        # the interval
        y = b[i]
         
        # Push current interval and index into tup
        tup.append(((x,y),i))
         
    # Sort the vector based on l-value
    # of the intervals
    tup.sort()
     
    # Stores r-value of current interval
    curr = tup[0][0][1]
     
    # Stores index of current interval
    currPos = tup[0][1]
     
    # Traverse the vector, tup[]
    for i in range(1,N) :
         
        # Stores l-value of previous interval
        Q = tup[i - 1][0][0]
         
        # Stores l-value of current interval
        R = tup[i][0][0]
         
        # If Q and R are equal
        if Q == R :
             
            # Print the index of interval
            if tup[i - 1][0][1] < tup[i][0][1] :
                 
                print(tup[i - 1][1], tup[i][1])
                 
            else :
                 
                print(tup[i][1], tup[i - 1][1])
                 
            return
         
        # Stores r-value of current interval
        T = tup[i][0][1]
         
        # If T is less than or equal to curr
        if (T <= curr) :
             
            print(tup[i][1], currPos)
             
            return
        else :
             
            # Update curr
            curr = T
             
            # Update currPos
            currPos = tup[i][1]
             
    # If such intervals found
    print("-1", "-1", end = "")
     
# Given l-value of segments
a = [ 1, 2, 3, 2, 2 ]
 
# Given r-value of segments
b = [ 5, 10, 10, 2, 15 ]
 
# Given size
N = len(a)
 
# Function Call
findOverlapSegement(N, a, b)
 
# This code is contributed by divyesh072019

C#

// C# program to implement 
// the above approach 
using System;
using System.Collections.Generic;
class GFG {
 
  // Function to find a pair(i, j) such that 
  // i-th interval lies within the j-th interval 
  static void findOverlapSegement(int N, int[] a, int[] b) 
  { 
 
    // Store interval and index of the interval 
    // in the form of { {l, r}, index } 
    List<Tuple<Tuple<int,int>, int>> tup = new List<Tuple<Tuple<int,int>, int>>();
 
    // Traverse the array, arr[][] 
    for (int i = 0; i < N; i++) { 
 
      int x, y; 
 
      // Stores l-value of 
      // the interval 
      x = a[i]; 
 
      // Stores r-value of 
      // the interval 
      y = b[i]; 
 
      // Push current interval and index into tup 
      tup.Add(new Tuple<Tuple<int,int>, int>(new Tuple<int, int>(x, y), i)); 
    } 
 
    // Sort the vector based on l-value 
    // of the intervals 
    tup.Sort(); 
 
    // Stores r-value of current interval 
    int curr = tup[0].Item1.Item2; 
 
    // Stores index of current interval 
    int currPos = tup[0].Item2; 
 
    // Traverse the vector, tup[] 
    for (int i = 1; i < N; i++) { 
 
      // Stores l-value of previous interval 
      int Q = tup[i - 1].Item1.Item1; 
 
      // Stores l-value of current interval 
      int R = tup[i].Item1.Item1; 
 
      // If Q and R are equal 
      if (Q == R) { 
 
        // Print the index of interval 
        if (tup[i - 1].Item1.Item2 < tup[i].Item1.Item2) 
          Console.Write(tup[i - 1].Item2 + " " + tup[i].Item2); 
 
        else
          Console.Write(tup[i].Item2 + " " + tup[i - 1].Item2); 
 
        return; 
      } 
 
      // Stores r-value of current interval 
      int T = tup[i].Item1.Item2; 
 
      // If T is less than or equal to curr 
      if (T <= curr) { 
        Console.Write(tup[i].Item2 + " " + currPos); 
        return; 
      } 
      else { 
 
        // Update curr 
        curr = T; 
 
        // Update currPos 
        currPos = tup[i].Item2; 
      } 
    } 
 
    // If such intervals found 
    Console.Write("-1 -1"); 
  }     
 
  // Driver code
  static void Main()
  {
 
    // Given l-value of segments 
    int[] a = { 1, 2, 3, 2, 2 }; 
 
    // Given r-value of segments 
    int[] b = { 5, 10, 10, 2, 15 }; 
 
    // Given size 
    int N = a.Length; 
 
    // Function Call 
    findOverlapSegement(N, a, b); 
  }
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find a pair(i, j) such that
// i-th interval lies within the j-th interval
function findOverlapSegement(N, a, b)
{
 
    // Store interval and index of the interval
    // in the form of { {l, r}, index }
    var tup = [];
 
    // Traverse the array, arr[][] 
    for (var i = 0; i < N; i++) {
 
          var x, y; 
 
          // Stores l-value of 
         // the interval 
          x = a[i]; 
 
          // Stores r-value of 
          // the interval 
          y = b[i]; 
 
          // Push current interval and index into tup 
        tup.push([[x, y], i]);
    }
 
    // Sort the vector based on l-value 
    // of the intervals 
    tup.sort((a,b) => 
    {
       if(a[0][0] == b[0][0])
       {
           return a[0][1] - b[0][1];
       }
        
       var tmp = (a[0][0] - b[0][0]);
       console.log(tmp);
 
       return (a[0][0] - b[0][0])
    });
 
    // Stores r-value of current interval 
    var curr = tup[0][0][1];
 
    // Stores index of current interval 
    var currPos = tup[0][1];
 
    // Traverse the vector, tup[] 
    for (var i = 1; i < N; i++) {
 
        // Stores l-value of previous interval 
        var Q = tup[i - 1][0][0];
 
        // Stores l-value of current interval 
        var R = tup[i][0][0];
 
        // If Q and R equal
        if (Q == R) {
 
            // If Y value of immediate previous
            // interval is less than Y value of
            // current interval
            if (tup[i - 1][0][1]
                < tup[i][0][1]) {
 
                // Print the index of interval 
                document.write(tup[i - 1][1] + " " + tup[i][1]);
                return;
            }
 
            else {
                document.write(tup[i][1] + " " + tup[i - 1][1]);
                return;
            }
        }
 
         // Stores r-value of current interval 
        var T = tup[i][0][1];
 
        // T is less than or equal to curr
        if (T <= curr) {
             document.write(tup[i][1] + " " + currPos);
             return;
        }
        else {
 
            // Update curr
            curr = T;
 
            // Update currPos
            currPos = tup[i][1];
        }
    }
 
    // If such intervals found 
    document.write("-1 -1"); 
}
 
// Driver Code
// Given l-value of segments 
    let a = [ 1, 2, 3, 2, 2 ]; 
 
    // Given r-value of segments 
    let b = [ 5, 10, 10, 2, 15 ]; 
 
    // Given size 
    let N = a.length; 
 
    // Function Call 
    findOverlapSegement(N, a, b);
 
// This code is contributed by Dharanendra L V.
</script>

Output:

3 0

Time Complexity: O(N * log(N))
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!