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 ith interval lies within the jth 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 ith interval lies within the jth interval or not. If found to be true, then print the pairs. Otherwise, print -1.
Time Complexity: O(N2)
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 intervalvoid 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 Codeint 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 intervaldef 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 segmentsa = [ 1, 2, 3, 2, 2 ]# Given r-value of segmentsb = [ 5, 10, 10, 2, 15 ]# Given sizeN = len(a)# Function CallfindOverlapSegement(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 intervalfunction 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
