Find all the intersecting pairs from a given array
Given n pairs (S[i], F[i]) where for every i, S[i]< F[i]. Two ranges are said to intersect if and only if either of them does not fully lie inside the other one that is only one point of a pair lies between the start and end of the other pair. We have to print all the intersecting ranges for each pair.
Note: All the endpoints that is F[i] are integers and are also unique. None of the pairs start and end at the same time. Also, no pair’s endpoint is the same as the start of the other. Examples:
Input : n = 6, v = {{9, 12}, {2, 11}, {1, 3}, {6, 10}, {5, 7}, {4, 8}} Output : {9, 12} is intersecting with: {6, 10} {2, 11} {2, 11} is intersecting with: {1, 3} {9, 12} {1, 3} is intersecting with: {2, 11} {6, 10} is intersecting with: {5, 7} {4, 8} {9, 12} {5, 7} is intersecting with: {6, 10} {4, 8} is intersecting with: {6, 10} Explanation: The first pair(9, 12) is intersecting with second(2, 11) and fourth(6, 10) pair. The second pair(2, 11) is intersecting with third(1, 3) and first(9, 12) pairs. The third pair(1, 3) is intersecting with the second(2, 11) pair. The forth pair(6, 10) is intersecting with fifth(5, 7), sixth(4, 8) and first(9, 12) pair. The fifth pair(5, 7) is intersecting with the fourth(6, 10) pair. The sixth pair(4, 8) is intersecting with the fourth(6, 10) pair. Input : n = 5, v = {1, 3}, {2, 4}, {5, 9}, {6, 8}, {7, 10}} Output : {1, 3} is intersecting with: {2, 4} {2, 4} is intersecting with: {1, 3} {5, 9} is intersecting with: {7, 10} {6, 8} is intersecting with: {7, 10} {7, 10} is intersecting with: {6, 8} {5, 9} Explanation: The first pair(1, 3) is intersecting with the second(2, 4) pair. The second pair(2, 4) is intersecting with the first(1, 3) pair. The third pair(5, 9) is intersecting with the fifth(7, 10) pair. The fourth pair(6, 8) is intersecting with the fifth(7, 10) pair. The fifth pair(7, 10) is intersecting with the third(5, 9) and fourth(6, 8) pair.
Approach: The above-mentioned problem can be solved by using sorting. Firstly, we have to insert every first element of the pair and the second element of the pair in a single vector along with the position of each. Then sort all the elements with respect to the first element of the pair. After that use a set data structure for second elements in the pair. Then we have to iterate in the vector in which we have stored the first and second element with their respective positions and if the first element is found then compute all ranges that are intersecting with the current pair from the set and if the second element of the pair is encountered then simply erase that second pair from the set. Otherwise add the second element of the current pair. Below is the implementation of above approach:
CPP
// CPP Program to Find all the // intersecting pairs from a given array #include <bits/stdc++.h> using namespace std; // Function that print intersecting pairs // for each pair in the vector void findIntersection(vector<pair< int , int > > v, int n) { vector<pair< int , int > > data; vector<vector< int > > answer(n); // Store each pair with their positions for ( int i = 0; i < n; i++) { data.push_back(make_pair(v[i].first, i)); data.push_back(make_pair(v[i].second, i)); } // Sort the vector with respect to // first element in the pair sort(data.begin(), data.end()); int curr = 0; // set data structure for keeping // the second element of each pair set<pair< int , int > > s; // Iterating data vector for ( auto it : data) { // check if all pairs are taken if (curr >= n) break ; // check if current value is a second element // then remove it from the set if (s.count(it)) s.erase(it); else { // index of the current pair int i = it.second; // Computing the second element of current pair int j = v[i].second; // Iterating in the set for ( auto k : s) { // Check if the set element // has higher value than the current // element's second element if (k.first > j) break ; int index = k.second; answer[i].push_back(index); answer[index].push_back(i); curr++; // Check if curr is equal to // all available pairs or not if (curr >= n) break ; } // Insert second element // of current pair in the set s.insert(make_pair(j, i)); } } // Printing the result for ( int i = 0; i < n; i++) { cout << "{" << v[i].first << ", " << v[i].second << "}" << " is intersecting with: " ; for ( int j = 0; j < answer[i].size(); j++) cout << "{" << v[answer[i][j]].first << ", " << v[answer[i][j]].second << "}" << " " ; cout << "\n" ; } } // Driver Code int main() { // initialise the size of vector int n = 6; // initialise the vector vector<pair< int , int > > v = { { 9, 12 }, { 2, 11 }, { 1, 3 }, { 6, 10 }, { 5, 7 }, { 4, 8 } }; findIntersection(v, n); return 0; } |
Python3
# Python3 Program to Find all the # intersecting pairs from a given array # Function that print intersecting pairs # for each pair in the vector def findIntersection(v, n): data = []; answer = [ [] for _ in range (n) ] # Store each pair with their positions for i in range (n): data.append((v[i][ 0 ], i)); data.append((v[i][ 1 ], i)); # Sort the vector with respect to # first element in the pair data.sort() curr = 0 ; # set data structure for keeping # the second element of each pair s = set () # Iterating data vector for it in data: # check if all pairs are taken if (curr > = n): break ; # check if current value is a second element # then remove it from the set if it in s: s.discard(it) else : # index of the current pair i = it[ 1 ]; # Computing the second element of current pair j = v[i][ 1 ]; # Iterating in the set for k in sorted (s, key = lambda x : ( - x[ 1 ], - x[ 0 ])): # Check if the set element # has higher value than the current # element's second element if (k[ 0 ] > j): break ; index = k[ 1 ]; answer[i].append(index); answer[index].append(i); curr + = 1 ; # Check if curr is equal to # all available pairs or not if (curr > = n): break ; # Insert second element # of current pair in the set if (j, i) not in s: s.add((j, i)) # Printing the result for i in range (n): print (v[i], "is intersecting with: " , end = ""); for j in range ( len (answer[i])): print (v[answer[i][j]], end = " " ); print () # Driver Code # initialise the size of vector n = 6 ; # initialise the vector v = [[ 9 , 12 ], [ 2 , 11 ], [ 1 , 3 ], [ 6 , 10 ], [ 5 , 7 ], [ 4 , 8 ]]; findIntersection(v, n); # This code is contributed by phasing17. |
C#
// C# Program to Find all the // intersecting Tuples from a given array using System; using System.Linq; using System.Collections.Generic; class GFG { // Function that print intersecting Tuples // for each Tuple in the List static void findIntersection(List<Tuple< int , int > > v, int n) { List<Tuple< int , int > > data = new List<Tuple< int , int > >(); List<List< int > > answer = new List<List< int > >(); for ( int i = 0; i < n; i++) answer.Add( new List< int >()); // Store each Tuple with their positions for ( int i = 0; i < n; i++) { data.Add(Tuple.Create(v[i].Item1, i)); data.Add(Tuple.Create(v[i].Item2, i)); } // Sort the List with respect to // Item1 element in the Tuple data.Sort(); int curr = 0; // set data structure for keeping // the Item2 element of each Tuple SortedSet<Tuple< int , int > > s = new SortedSet<Tuple< int , int > >(); // Iterating data List foreach ( var it in data) { // check if all Tuples are taken if (curr >= n) break ; // check if current value is a Item2 element // then remove it from the set if (s.Contains(it)) s.Remove(it); else { // index of the current Tuple int i = it.Item2; // Computing the Item2 element of current // Tuple int j = v[i].Item2; // Iterating in the set foreach ( var k in s) { // Check if the set element // has higher value than the current // element's Item2 element if (k.Item1 > j) break ; int index = k.Item2; answer[i].Add(index); answer[index].Add(i); curr++; // Check if curr is equal to // all available Tuples or not if (curr >= n) break ; } // Insert Item2 element // of current Tuple in the set s.Add(Tuple.Create(j, i)); } } // Printing the result for ( int i = 0; i < n; i++) { Console.Write( "{" + v[i].Item1 + ", " + v[i].Item2 + "}" + " is intersecting with: " ); for ( int j = 0; j < answer[i].Count; j++) Console.Write( "{" + v[answer[i][j]].Item1 + ", " + v[answer[i][j]].Item2 + "}" + " " ); Console.Write( "\n" ); } } // Driver Code public static void Main( string [] args) { // initialise the size of List int n = 6; // initialise the List List<Tuple< int , int > > v = new List<Tuple< int , int > >(); v.Add(Tuple.Create(9, 12)); v.Add(Tuple.Create(2, 11)); v.Add(Tuple.Create(1, 3)); v.Add(Tuple.Create(6, 10)); v.Add(Tuple.Create(5, 7)); v.Add(Tuple.Create(4, 8)); findIntersection(v, n); } } // This code is contributed by phasing17. |
Javascript
// JS Program to Find all the // intersecting pairs from a given array // Function that print intersecting pairs // for each pair in the vector function findIntersection(v, n) { let data = []; let answer = new Array(n); for ( var i = 0; i < n; i++) answer[i] = [] // Store each pair with their positions for ( var i = 0; i < n; i++) { data.push([v[i][0], i]); data.push([v[i][1], i]); } // Sort the vector with respect to // first element in the pair data.sort( function (a, b) { return (-a[0] + b[0]); }) var curr = 0; // set data structure for keeping // the second element of each pair let s = [] // Iterating data vector for ( var it of data) { // check if all pairs are taken if (curr >= n) break ; s.sort( function (a, b) { return (a[0] - b[0]); }) // check if current value is a second element // then remove it from the set let pos = s.indexOf(it) if (pos != -1) s.splice(pos, 1); else { s.sort( function (a, b) { return (a[0] == b[0]) ? (a[1] - b[1]) : (a[0] - b[0]); }) // index of the current pair var i = it[1]; // Computing the second element of current pair var j = v[i][1]; // Iterating in the set for ( var k of s) { // Check if the set element // has higher value than the current // element's second element if (k[0] > j) break ; var index = k[1]; answer[i].push(index); answer[index].push(i); curr++; // Check if curr is equal to // all available pairs or not if (curr >= n) break ; } // Insert second element // of current pair in the set if (s.indexOf([j, i]) == -1 ) s.push([j, i]) } } // Printing the result for ( var i = 0; i < n; i++) { process.stdout.write( "{" + v[i][0] + ", " + v[i][1] + "}" + " is intersecting with: " ); for ( var j = 0; j < answer[i].length; j++) process.stdout.write( "{" + v[answer[i][j]][0] + ", " + v[answer[i][j]][1] + "}" + " " ); process.stdout.write( "\n" ); } } // Driver Code // initialise the size of vector let n = 6; // initialise the vector let v = [[ 9, 12 ], [2, 11 ], [ 1, 3 ], [ 6, 10 ], [ 5, 7 ], [ 4, 8 ]]; findIntersection(v, n); // This code is contributed by phasing17. |
Java
import java.util.*; // Pair class with two generic types A and B class Pair<A, B> { public A first; public B second; // Constructor for Pair class public Pair(A first, B second) { this .first = first; this .second = second; } } public class IntervalIntersection { // Method to find the intersection of intervals public static void findIntersection(List<Pair<Integer, Integer> > v, int n) { // Create two lists, one to hold the interval data // and the other to hold the answer List<Pair<Integer, Integer> > data = new ArrayList<>(); List<List<Integer> > answer = new ArrayList<>(); // Loop through each interval for ( int i = 0 ; i < n; i++) { // Add the start and end of the interval to the // data list data.add( new Pair<Integer, Integer>( v.get(i).first, i)); data.add( new Pair<Integer, Integer>( v.get(i).second, i)); // Add a new empty list to the answer list for // each interval answer.add( new ArrayList<>()); } // Sort the data list by the first element of each // pair (i.e., the start of each interval) Collections.sort( data, new Comparator<Pair<Integer, Integer> >() { public int compare( Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) { return p1.first.compareTo(p2.first); } }); int curr = 0 ; // Use a TreeSet to keep track of the current // intervals The TreeSet is sorted by the second // element of each pair (i.e., the index of the // interval in the original list) Set<Pair<Integer, Integer> > s = new TreeSet<>( new Comparator<Pair<Integer, Integer> >() { public int compare( Pair<Integer, Integer> p1, Pair<Integer, Integer> p2) { if (p1.first.equals(p2.first)) { return p1.second.compareTo( p2.second); } return p1.first.compareTo(p2.first); } }); // Loop through each element in the sorted data list for (Pair<Integer, Integer> it : data) { // If all intervals have been processed, break // out of the loop if (curr >= n) break ; // If the current interval is in the TreeSet, // remove it if (s.contains(it)) s.remove(it); else { // Otherwise, add the current interval to // the TreeSet int i = it.second; int j = v.get(i).second; // Loop through all intervals in the TreeSet // that intersect with the current interval for (Pair<Integer, Integer> k : s) { if (k.first > j) break ; int index = k.second; // Add the intersecting interval to the // answer list for both intervals answer.get(i).add(index); answer.get(index).add(i); curr++; if (curr >= n) break ; } // Add the current interval to the TreeSet s.add( new Pair<Integer, Integer>(j, i)); } } // Print the result of the intersection for ( int i = 0 ; i < n; i++) { System.out.print( "{" + v.get(i).first + ", " + v.get(i).second + "}" + " is intersecting with: " ); for ( int j = 0 ; j < answer.get(i).size(); j++) System.out.print( "{" + v.get(answer.get(i).get(j)).first + ", " + v.get(answer.get(i).get(j)).second + "}" + " " ); System.out.println(); } } // Driver Code public static void main(String[] args) { int n = 6 ; List<Pair<Integer, Integer> > v = new ArrayList<>(); v.add( new Pair<Integer, Integer>( 9 , 12 )); v.add( new Pair<Integer, Integer>( 2 , 11 )); v.add( new Pair<Integer, Integer>( 1 , 3 )); v.add( new Pair<Integer, Integer>( 6 , 10 )); v.add( new Pair<Integer, Integer>( 5 , 7 )); v.add( new Pair<Integer, Integer>( 4 , 8 )); findIntersection(v, n); } } |
{9, 12} is intersecting with: {6, 10} {2, 11} {2, 11} is intersecting with: {1, 3} {9, 12} {1, 3} is intersecting with: {2, 11} {6, 10} is intersecting with: {5, 7} {4, 8} {9, 12} {5, 7} is intersecting with: {6, 10} {4, 8} is intersecting with: {6, 10}
Time Complexity: O(n * log2n), where n is the size of the input vector. This is because the code involves sorting the vector based on the first element of each pair, which takes O(n * log2n) time. The subsequent loop iterates over the sorted vector and performs set operations, which takes O(n * log2n) time in total. Finally, the code prints the output, which takes O(n) time. Therefore, the overall time complexity of the code is dominated by the sorting operation and is O(n * log2n).