Given two arrays X[] and Y[], representing points on X and Y number lines, such that every similar-indexed array element forms a line segment, i.e. X[i] and Y[i] forms a line segment, the task is to find the maximum number of line segments that can be selected from the given array.
Examples:
Input: X[] = {0, 3, 4, 1, 2}, Y[] = {3, 2, 0, 1, 4}
Output: 3
Explanation: The set of line segments are {{1, 1}, {4, 0}, {0, 3}}.Input: X[] = {1, 2, 0}, Y[] = {2, 0, 1}
Output: 2
Explanation: The set of line segments is {{1, 2}, {2, 0}}.
Approach: The problem can be solved using the observation that the intersection between two line-segments (i, j) occurs only when X[i] < X[j] and Y[i] > Y[j] or vice-versa. Therefore, the problem can be solved using Sorting along with Binary search, using Sets can be used to find such line segments.
Follow the steps below to solve the given problem:
- Initialize a vector of pairs, say p to store pairs {X[i], Y[i]} as an element.
- Sort the vector of pairs p in ascending order of points on X number line, so every line segment i satisfies the first condition for the intersection i.e X[k] < X[i] where k < i.
- Initialize a Set, say s, to store the values of Y[i] in descending order.
- From the first element from p, push the Y-coordinate (i.e p[0].second) into the set.
- Iterate over all the elements of p, and for each element:
- Perform a binary search to find the lower_bound of p[i].second.
- If there is no lower bound obtained, that means that p[i].second is smaller than all the elements present in the Set. This satisfies the second condition that Y[i] < Y[k] where k < i, so push p[i].second into the Set.
- If a lower bound is found, then remove it and push p[i].second into the Set.
- Finally, return the size of the set that as the result.
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 maximum number of// intersecting line segments possibleint solve(int N, int X[], int Y[]){ // Stores pairs of line // segments {X[i], Y[i]) vector<pair<int, int> > p; for (int i = 0; i < N; i++) { // Push {X[i], Y[i]} into p p.push_back({ X[i], Y[i] }); } // Sort p in ascending order // of points on X number line sort(p.begin(), p.end()); // Stores the points on Y number // line in descending order set<int, greater<int> > s; // Insert the first Y point from p s.insert(p[0].second); for (int i = 0; i < N; i++) { // Binary search to find the // lower bound of p[i].second auto it = s.lower_bound(p[i].second); // If lower_bound doesn't exist if (it == s.end()) { // Insert p[i].second into the set s.insert(p[i].second); } else { // Erase the next lower //_bound from the set s.erase(*it); // Insert p[i].second // into the set s.insert(p[i].second); } } // Return the size of the set // as the final result return s.size();}// Driver Codeint main(){ // Given Input int N = 3; int X[] = { 1, 2, 0 }; int Y[] = { 2, 0, 1 }; // Function call to find the maximum // number of intersecting line segments int maxintersection = solve(N, X, Y); cout << maxintersection;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to find the maximum number of// intersecting line segments possiblestatic int solve(int N, int X[], int Y[]){ // Stores pairs of line // segments {X[i], Y[i]) ArrayList<int[]> p = new ArrayList<>(); for(int i = 0; i < N; i++) { // Add {X[i], Y[i]} into p p.add(new int[] { X[i], Y[i] }); } // Sort p in ascending order // of points on X number line Collections.sort(p, (p1, p2) -> { if (p1[0] != p2[0]) return p1[0] - p2[0]; return p1[1] - p2[1]; }); // Stores the points on Y number // line in ascending order TreeSet<Integer> s = new TreeSet<>(); // Insert the first Y point from p s.add(p.get(0)[1]); for(int i = 0; i < N; i++) { // Binary search to find the // floor value of p.get(i)[1] Integer it = s.floor(p.get(i)[1]); // If floor value doesn't exist if (it == null) { // Insert p.get(i)[1] into the set s.add(p.get(i)[1]); } else { // Erase the next floor // value from the set s.remove(it); // Insert p.get(i)[1] // into the set s.add(p.get(i)[1]); } } // Return the size of the set // as the final result return s.size();}// Driver Codepublic static void main(String[] args){ // Given Input int N = 3; int X[] = { 1, 2, 0 }; int Y[] = { 2, 0, 1 }; // Function call to find the maximum // number of intersecting line segments int maxintersection = solve(N, X, Y); System.out.println(maxintersection);}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approachfrom bisect import bisect_left# Function to find the maximum number of# intersecting line segments possibledef solve(N, X, Y): # Stores pairs of line # segments {X[i], Y[i]) p = [] for i in range(N): # Push {X[i], Y[i]} into p p.append([X[i], Y[i]]) # Sort p in ascending order # of points on X number line p = sorted(p) # Stores the points on Y number # line in descending order s = {} # Insert the first Y pofrom p s[p[0][1]] = 1 for i in range(N): # Binary search to find the # lower bound of p[i][1] arr = list(s.keys()) it = bisect_left(arr, p[i][1]) # If lower_bound doesn't exist if (it == len(s)): # Insert p[i][1] into the set s[p[i][1]] = 1 else: # Erase the next lower # _bound from the set del s[arr[it]] # Insert p[i][1] # into the set s[p[i][1]] = 1 # Return the size of the set # as the final result return len(s)# Driver Codeif __name__ == '__main__': # Given Input N = 3 X = [1, 2, 0] Y = [2, 0, 1] # Function call to find the maximum # number of intersecting line segments maxintersection = solve(N, X, Y) print (maxintersection)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;using System.Linq;class GFG{ // Function to find the maximum number of // intersecting line segments possible static int solve(int N, int[] X, int[] Y) { // Stores pairs of line // segments {X[i], Y[i]) var p = new List<int[]>(); for (int i = 0; i < N; i++) { // Add {X[i], Y[i]} into p p.Add(new int[] { X[i], Y[i] }); } // Sort p in ascending order // of points on X number line p.Sort((p1, p2) => { if (p1[0] != p2[0]) return p1[0] - p2[0]; return p1[1] - p2[1]; }); // Stores the points on Y number // line in ascending order var s = new SortedSet<int>(); // Insert the first Y point from p s.Add(p[0][1]); for (int i = 0; i < N; i++) { // Binary search to find the // floor value of p[i][1] int it = s.GetViewBetween(int.MinValue, p[i][1]).Max; // If floor value doesn't exist if (it == default) { // Insert p[i][1] into the set s.Add(p[i][1]); } else { // Erase the next floor // value from the set s.Remove(it); // Insert p[i][1] // into the set s.Add(p[i][1]); } } // Return the size of the set // as the final result return s.Count; } // Driver Code static void Main(string[] args) { // Given Input int N = 3; int[] X = { 1, 2, 0 }; int[] Y = { 2, 0, 1 }; // Function call to find the maximum // number of intersecting line segments int maxintersection = solve(N, X, Y); Console.WriteLine(maxintersection); }}// This code is contributed by phasing17 |
Javascript
// Function to find the maximum number of// intersecting line segments possiblefunction solve(N, X, Y) { // Stores pairs of line // segments {X[i], Y[i]) const p = []; for (let i = 0; i < N; i++) { // Push {X[i], Y[i]} into p p.push([X[i], Y[i]]); } // Sort p in ascending order // of points on X number line p.sort((a, b) => a[0] - b[0]); // Stores the points on Y number // line in descending order const s = {}; // Insert the first Y pofrom p s[p[0][1]] = 1; for (let i = 0; i < N; i++) { // Binary search to find the // lower bound of p[i][1] const arr = Object.keys(s).map((key) => parseInt(key, 10)).sort((a, b) => b - a); let it = arr.findIndex((elem) => elem <= p[i][1]); if (it < 0) it = arr.length; // If lower_bound doesn't exist if (it === arr.length) { // Insert p[i][1] into the set s[p[i][1]] = 1; } else { // Erase the next lower // _bound from the set delete s[arr[it]]; // Insert p[i][1] // into the set s[p[i][1]] = 1; } } // Return the size of the set // as the final result return Object.keys(s).length;}// Given Inputconst N = 3;const X = [1, 2, 0];const Y = [2, 0, 1];// Function call to find the maximum// number of intersecting line segmentsconst maxintersection = solve(N, X, Y);console.log(maxintersection);// This code is contributed by phasing17. |
Output:
2
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!
