Maximizar el recuento de segmentos de línea que se cruzan

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:

  1. Inicialice un vector de pares , digamos p para almacenar los pares {X[i], Y[i]} como un elemento.
  2. 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 .
  3. Inicialice un Set , digamos s , para almacenar los valores de Y[i] en orden descendente.
  4. Desde el primer elemento de p , inserte la coordenada Y (es decir , p[0].segundo ) en el conjunto.
  5. Iterar sobre todos los elementos de p , y para cada elemento:
  6. 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
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *