Dadas dos arrays X[] e Y[] , que representan puntos en las rectas numéricas X e Y , de modo que cada elemento de array indexado de forma similar forma un segmento de recta, es decir, X[i] e Y[i] forman un segmento de recta, la tarea es encontrar el número máximo de segmentos de línea que se pueden seleccionar de la array dada.
Ejemplos:
Entrada: X[] = {0, 3, 4, 1, 2}, Y[] = {3, 2, 0, 1, 4}
Salida: 3
Explicación: El conjunto de segmentos de línea son {{1, 1} , {4, 0}, {0, 3}}.Entrada: X[] = {1, 2, 0}, Y[] = {2, 0, 1}
Salida: 2
Explicación: El conjunto de segmentos de línea es {{1, 2}, {2, 0}}.
Enfoque: el problema se puede resolver utilizando la observación de que la intersección entre dos segmentos de línea (i, j) ocurre solo cuando X[i] < X[j] e Y[i] > Y[j] o viceversa . Por lo tanto, el problema se puede resolver usando la clasificación junto con la búsqueda binaria , y los conjuntos se pueden usar para encontrar dichos segmentos de línea.
Siga los pasos a continuación para resolver el problema dado:
- Inicialice un vector de pares , digamos p para almacenar los pares {X[i], Y[i]} como un elemento.
- Ordene el vector de pares p en orden ascendente de puntos en la recta numérica X, de modo que cada segmento de recta i satisfaga la primera condición para la intersección, es decir , X[k] < X[i] donde k < i .
- Inicialice un Set , digamos s , para almacenar los valores de Y[i] en orden descendente.
- Desde el primer elemento de p , inserte la coordenada Y (es decir , p[0].segundo ) en el conjunto.
- Iterar sobre todos los elementos de p , y para cada elemento:
- Realice una búsqueda binaria para encontrar el límite inferior de p[i].segundo .
- Si no se obtiene un límite inferior , eso significa que p[i].segundo es más pequeño que todos los elementos presentes en el Conjunto . Esto satisface la segunda condición de que Y[i] < Y[k] donde k < i , así que inserte p[i].segundo en el Set .
- Si se encuentra un límite inferior, elimínelo y presione p[i].segundo en el Set .
- Finalmente, devuelva el tamaño del conjunto que como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum number of // intersecting line segments possible int 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 Code int 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 approach import java.io.*; import java.lang.*; import java.util.*; 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]) 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 Code public 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 approach from bisect import bisect_left # Function to find the maximum number of # intersecting line segments possible def 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 Code if __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
2
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA