Given a 2D array segments[][] where each segment is of the form [L, R] representing (X, Y) co-ordinates, the task is to find a segment that overlaps with maximum number of segments.
Examples:
Input: segments[][] = {{1, 4}, {2, 3}, {3, 6}}
Output: {3, 6}
Explanation: Every segment overlaps with all other segments. Therefore, print any one of them.Input: segments[][] = {{1, 2}, {3, 8}, {4, 5}, {6, 7}, {9, 10}}
Output: {3, 8}
Explanation: The segment {3, 8} overlaps {4, 5} and {6, 7}.
Approach: Follow the steps below to solve the problem:
- It is clear that in a segment [currL, currR], all the ‘R’ values of the remaining segments which are less than ‘currL’ and all the ‘L’ values of the remaining segments which are greater than ‘currR’ will not be counted to the answer.
- Store all the ‘R’ values in an array and perform a binary search to find all the ‘R’ values less than ‘currL’ and similarly do this to find all the ‘L’ values greater than ‘currR’.
- Traverse the array and update the segment coordinates with the maximum intersection at each iteration.
- Print the segment with the maximum intersection.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the segment which// overlaps with maximum number of segmentsvoid maxIntersection(int segments[][2], int N){ // 'L' & 'R' co-ordinates of all // segments are stored in lvalues & rvalues vector<int> rvalues(N), lvalues(N); // Assign co-ordinates for (int i = 0; i < N; ++i) { lvalues[i] = segments[i][0]; rvalues[i] = segments[i][1]; } // Co-ordinate compression sort(lvalues.begin(), lvalues.end()); sort(rvalues.begin(), rvalues.end()); // Stores the required segment pair<int, int> answer = { -1, -1 }; // Stores the current maximum // number of intersections int numIntersections = 0; for (int i = 0; i < N; ++i) { // Find number of 'R' coordinates // which are less than the 'L' // value of the current segment int lesser = lower_bound(rvalues.begin(), rvalues.end(), segments[i][0]) - rvalues.begin(); // Find number of 'L' coordinates // which are greater than the 'R' // value of the current segment int greater = max( 0, N - (int)(upper_bound(lvalues.begin(), lvalues.end(), segments[i][1]) - lvalues.begin())); // Segments excluding 'lesser' and // 'greater' gives the number of // intersections if ((N - lesser - greater) >= numIntersections) { answer = { segments[i][0], segments[i][1] }; // Update the current maximum numIntersections = (N - lesser - greater); } } // Print segment coordinates cout << answer.first << " " << answer.second;}// Driver Codeint main(){ // Given segments int segments[][2] = { { 1, 4 }, { 2, 3 }, { 3, 6 } }; // Size of segments array int N = sizeof(segments) / sizeof(segments[0]); maxIntersection(segments, N);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the segment which// overlaps with maximum number of segmentsstatic void maxIntersection(int segments[][], int N){ // 'L' & 'R' co-ordinates of all // segments are stored in lvalues & rvalues int []rvalues = new int[N]; int []lvalues = new int[N]; // Assign co-ordinates for (int i = 0; i < N; ++i) { lvalues[i] = segments[i][0]; rvalues[i] = segments[i][1]; } // Co-ordinate compression Arrays.sort(lvalues); Arrays.sort(rvalues); // Stores the required segment int []answer = { -1, -1 }; // Stores the current maximum // number of intersections int numIntersections = 0; for (int i = 0; i < N; ++i) { // Find number of 'R' coordinates // which are less than the 'L' // value of the current segment int lesser = lower_bound(rvalues, 0, segments.length, segments[i][0]); // Find number of 'L' coordinates // which are greater than the 'R' // value of the current segment int greater = Math.max( 0, N-(upper_bound(lvalues, 0, segments.length, segments[i][1]))); // Segments excluding 'lesser' and // 'greater' gives the number of // intersections if ((N - lesser - greater) >= numIntersections) { answer = new int[]{ segments[i][0], segments[i][1] }; // Update the current maximum numIntersections = (N - lesser - greater); } } // Print segment coordinates System.out.print(answer[0]+ " " + answer[1]);}static int lower_bound(int[] a, int low, int high, int element){ while(low < high){ int middle = low + (high - low)/2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}static int upper_bound(int[] a, int low, int high, int element){ while(low < high){ int middle = low + (high - low)/2; if(a[middle] > element) high = middle; else low = middle + 1; } return low;}// Driver Codepublic static void main(String[] args){ // Given segments int segments[][] = { { 1, 4 }, { 2, 3 }, { 3, 6 } }; // Size of segments array int N = segments.length; maxIntersection(segments, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find the segment which# overlaps with maximum number of segmentsfrom bisect import bisect_leftfrom bisect import bisect_rightdef maxIntersection(segments, N): # 'L' & 'R' co-ordinates of all # segments are stored in lvalues & rvalues rvalues = [] lvalues = [] # Assign co-ordinates for i in range(N): lvalues.append(segments[i][0]) rvalues.append(segments[i][1]) # Co-ordinate compression lvalues.sort() rvalues.sort() # Stores the required segment answer = [-1, -1] # Stores the current maximum # number of intersections numIntersections = 0 for i in range(N): # Find number of 'R' coordinates # which are less than the 'L' # value of the current segment lesser = bisect_left(rvalues, segments[i][0], 0, len(segments)) # Find number of 'L' coordinates # which are greater than the 'R' # value of the current segment greater = max( 0, N - (bisect_right(lvalues, segments[i][1], 0, len(segments)))) # Segments excluding 'lesser' and # 'greater' gives the number of # intersections if ((N - lesser - greater) >= numIntersections): answer = [segments[i][0], segments[i][1]] # Update the current maximum numIntersections = (N - lesser - greater) # Print segment coordinates print(answer[0], answer[1])# Driver Code# Given segmentssegments = [[1, 4], [2, 3], [3, 6]]# Size of segments arrayN = len(segments)maxIntersection(segments, N)# The code is contributed by Gautam goel (gautamgoel962) |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the segment which // overlaps with maximum number of segments static void maxIntersection(int [,]segments, int N) { // 'L' & 'R' co-ordinates of all // segments are stored in lvalues & rvalues int []rvalues = new int[N]; int []lvalues = new int[N]; // Assign co-ordinates for (int i = 0; i < N; ++i) { lvalues[i] = segments[i,0]; rvalues[i] = segments[i,1]; } // Co-ordinate compression Array.Sort(lvalues); Array.Sort(rvalues); // Stores the required segment int []answer = { -1, -1 }; // Stores the current maximum // number of intersections int numIntersections = 0; for (int i = 0; i < N; ++i) { // Find number of 'R' coordinates // which are less than the 'L' // value of the current segment int lesser = lower_bound(rvalues, 0, segments.GetLength(0), segments[i,0]); // Find number of 'L' coordinates // which are greater than the 'R' // value of the current segment int greater = Math.Max( 0, N-(upper_bound(lvalues, 0, segments.GetLength(0), segments[i,1]))); // Segments excluding 'lesser' and // 'greater' gives the number of // intersections if ((N - lesser - greater) >= numIntersections) { answer = new int[]{ segments[i,0], segments[i,1] }; // Update the current maximum numIntersections = (N - lesser - greater); } } // Print segment coordinates Console.Write(answer[0]+ " " + answer[1]); } static int lower_bound(int[] a, int low, int high, int element) { while(low < high) { int middle = low + (high - low)/2; if(element > a[middle]) low = middle + 1; else high = middle; } return low; } static int upper_bound(int[] a, int low, int high, int element) { while(low < high) { int middle = low + (high - low)/2; if(a[middle] > element) high = middle; else low = middle + 1; } return low; } // Driver Code public static void Main(String[] args) { // Given segments int [,]segments = { { 1, 4 }, { 2, 3 }, { 3, 6 } }; // Size of segments array int N = segments.GetLength(0); maxIntersection(segments, N); }}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach function lower_bound(a , low , high , element) { while (low < high) { var middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } function upper_bound(a , low , high , element) { while (low < high) { var middle = low + (high - low) / 2; if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Function to find the segment which // overlaps with maximum number of segments function maxIntersection(segments , N) { // 'L' & 'R' co-ordinates of all // segments are stored in lvalues & rvalues let rvalues = Array(N).fill(0); let lvalues = Array(N).fill(0); // Assign co-ordinates for (i = 0; i < N; ++i) { lvalues[i] = segments[i][0]; rvalues[i] = segments[i][1]; } // Co-ordinate compression lvalues.sort((a,b)=>a-b); rvalues.sort((a,b)=>a-b); // Stores the required segment let answer = [ -1, -1 ]; // Stores the current maximum // number of intersections var numIntersections = 0; for (var i = 0; i < N; ++i) { // Find number of 'R' coordinates // which are less than the 'L' // value of the current segment var lesser = lower_bound(rvalues, 0, segments.length, segments[i][0]); // Find number of 'L' coordinates // which are greater than the 'R' // value of the current segment var greater = Math.max(0, N - (upper_bound(lvalues, 0, segments.length, segments[i][1]))); // Segments excluding 'lesser' and // 'greater' gives the number of // intersections if ((N - lesser - greater) >= numIntersections) { answer = [ segments[i][0], segments[i][1] ]; // Update the current maximum numIntersections = (N - lesser - greater); } } // Print segment coordinates document.write(answer[0] + " " + answer[1]); } // Driver Code // Given segments var segments = [ [ 1, 4 ], [ 2, 3 ], [ 3, 6 ] ]; // Size of segments array var N = segments.length; maxIntersection(segments, N);// This code contributed by umadevi9616</script> |
Output:
3 6
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!
