Dada una array arr[] que consta de N pares de tipo {L, R} , cada uno de los cuales representa un segmento en el eje X , la tarea es encontrar el número máximo de intersecciones que tiene un segmento con otros segmentos.
Ejemplos:
Entrada: arr[] = {{1, 6}, {5, 5}, {2, 3}}
Salida: 2
Explicación:
A continuación se muestra el recuento de cada segmento que se superpone con los otros segmentos:
- El primer segmento [1, 6] se cruza con 2 segmentos [5, 5] y [2, 3].
- El segundo segmento [5, 5] se cruza con 1 segmento [1, 6].
- El tercer segmento [2, 3] se cruza con 1 segmento [1, 6].
Por lo tanto, el número máximo de intersecciones entre todos los segmentos es 2.
Entrada: arr[][] = {{4, 8}, {3, 6}, {7, 11}, {9, 10}}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar sobre todos los segmentos y para cada segmento contar el número de intersecciones al verificarlo con todos los demás segmentos y luego imprimir el máximo entre todos los recuentos de intersecciones obtenidos.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- El enfoque anterior se puede optimizar recorriendo cada segmento y calculando la cantidad de segmentos que no se cruzan con el segmento actual utilizando la búsqueda binaria y, a partir de ahí, encuentre la cantidad de segmentos que se cruzan con el segmento actual.
- Supongamos que [L, R] es el segmento actual y [P, Q] es otro segmento, entonces, el segmento [L, R] no se cruza con el segmento [P, Q] si Q < L o P > R.
- Supongamos que X es el número de segmentos que no se intersecan con el segmento [L, R] , entonces, la cantidad de segmentos que se intersecan con el segmento [L, R] = (N – 1 – X) .
Siga los pasos a continuación para resolver el problema:
- Almacene todos los puntos de la izquierda de los segmentos en una array, por ejemplo , L[] y todos los puntos de la derecha de los segmentos en la array, por ejemplo, R[] .
- Ordene las arrays L[] y R[] en orden ascendente .
- Inicialice una variable, diga contar como 0 para almacenar el recuento de la intersección máxima que tiene un segmento.
- Recorra la array arr[] y realice los siguientes pasos:
- Calcule la cantidad de segmentos que le quedan al segmento actual {arr[i][0], arr[i][1]} usando lower_bound() y guárdelo en una variable, digamos cnt .
- Calcule el número de segmentos directamente al segmento actual {arr[i][0], arr[i][1]} usando upper_bound() e incremente el conteo de cnt por él.
- Actualice el valor de conteo como el máximo de conteo y (N – cnt – 1) .
- Después de completar los pasos anteriores, imprima el valor del conteo 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 intersections one segment has with
// all the other given segments
int maximumIntersections(int arr[][2],
int N)
{
// Stores the resultant maximum count
int count = 0;
// Stores the starting and the
// ending points
int L[N], R[N];
for (int i = 0; i < N; i++) {
L[i] = arr[i][0];
R[i] = arr[i][1];
}
// Sort arrays points in the
// ascending order
sort(L, L + N);
sort(R, R + N);
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
int l = arr[i][0];
int r = arr[i][1];
// Find the count of segments
// on left of ith segment
int x = lower_bound(R, R + N, l) - R;
// Find the count of segments
// on right of ith segment
int y = N - (upper_bound(L, L + N, r) - L);
// Find the total segments not
// intersecting with the current
// segment
int cnt = x + y;
// Store the count of segments
// that intersect with the
// ith segment
cnt = N - cnt - 1;
// Update the value of count
count = max(count, cnt);
}
// Return the resultant count
return count;
}
// Driver Code
int main()
{
int arr[][2] = { { 1, 6 }, { 5, 5 }, { 2, 3 } };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumIntersections(arr, N);
return 0;
}
Java
// java program for the above approach
import java.util.*;
class GFG
{static int lower_bound(int[] a, int low, int high, long element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int maximumIntersections(int [][]arr,
int N)
{
// Stores the resultant maximum count
int count = 0;
// Stores the starting and the
// ending points
int[] L = new int[N];
int[] R = new int[N];
for (int i = 0; i < N; i++) {
L[i] = arr[i][0];
R[i] = arr[i][1];
}
// Sort arrays points in the
// ascending order
Arrays.sort(L);
Arrays.sort(R);
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
int l = arr[i][0];
int r = arr[i][1];
// Find the count of segments
// on left of ith segment
int x = lower_bound(L, 0,N, l);
// Find the count of segments
// on right of ith segment
int y = N-lower_bound(R, 0,N, r+1);
// Find the total segments not
// intersecting with the current
// segment
int cnt = x + y;
// Store the count of segments
// that intersect with the
// ith segment
cnt = N - cnt - 1;
// Update the value of count
count = Math.max(count, cnt);
}
// Return the resultant count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[][] = { { 1, 6 }, { 5, 5 }, { 2, 3 } };
int N = arr.length;
System.out.println(maximumIntersections(arr, N));
}
}
// This code is contributed by stream_cipher.
Python3
# Python 3 program for the above approach from bisect import bisect_left, bisect_right def lower_bound(a, low, high, element): while(low < high): middle = low + (high - low) // 2 if(element > a[middle]): low = middle + 1 else: high = middle return low # Function to find the maximum number # of intersections one segment has with # all the other given segments def maximumIntersections(arr, N): # Stores the resultant maximum count count = 0 # Stores the starting and the # ending points L = [0]*N R = [0]*N for i in range(N): L[i] = arr[i][0] R[i] = arr[i][1] # Sort arrays points in the # ascending order L.sort() R.sort() # Traverse the array arr[] for i in range(N): l = arr[i][0] r = arr[i][1] # Find the count of segments # on left of ith segment x = lower_bound(L, 0, N, l) # Find the count of segments # on right of ith segment y = N-lower_bound(R, 0, N, r+1) # Find the total segments not # intersecting with the current # segment cnt = x + y # Store the count of segments # that intersect with the # ith segment cnt = N - cnt - 1 # Update the value of count count = max(count, cnt) # Return the resultant count return count # Driver Code if __name__ == "__main__": arr = [[1, 6], [5, 5], [2, 3]] N = len(arr) print(maximumIntersections(arr, N)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int lower_bound(int[] a, int low,
int high, long element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
static int maximumIntersections(int [,]arr,
int N)
{
// Stores the resultant maximum count
int count = 0;
// Stores the starting and the
// ending points
int[] L = new int[N];
int[] R = new int[N];
for(int i = 0; i < N; i++)
{
L[i] = arr[i, 0];
R[i] = arr[i, 1];
}
// Sort arrays points in the
// ascending order
Array.Sort(L);
Array.Sort(R);
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
int l = arr[i, 0];
int r = arr[i, 1];
// Find the count of segments
// on left of ith segment
int x = lower_bound(L, 0, N, l);
// Find the count of segments
// on right of ith segment
int y = N-lower_bound(R, 0, N, r + 1);
// Find the total segments not
// intersecting with the current
// segment
int cnt = x + y;
// Store the count of segments
// that intersect with the
// ith segment
cnt = N - cnt - 1;
// Update the value of count
count = Math.Max(count, cnt);
}
// Return the resultant count
return count;
}
// Driver Code
public static void Main()
{
int [,]arr = new int[3, 2]{ { 1, 6 },
{ 5, 5 },
{ 2, 3 } };
int N = 3;
Console.Write(maximumIntersections(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// Javascript program for the above approach
function lower_bound(a, low, high, element)
{
while(low < high)
{
let middle = low + Math.floor(
(high - low) / 2);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to find the maximum number
// of intersections one segment has with
// all the other given segments
function maximumLetersections(arr, N)
{
// Stores the resultant maximum count
let count = 0;
// Stores the starting and the
// ending points
let L = Array.from({length: N}, (_, i) => 0);
let R = Array.from({length: N}, (_, i) => 0);
for(let i = 0; i < N; i++)
{
L[i] = arr[i][0];
R[i] = arr[i][1];
}
// Sort arrays points in the
// ascending order
L.sort();
R.sort();
// Traverse the array arr[]
for(let i = 0; i < N; i++)
{
let l = arr[i][0];
let r = arr[i][1];
// Find the count of segments
// on left of ith segment
let x = lower_bound(L, 0, N, l);
// Find the count of segments
// on right of ith segment
let y = N-lower_bound(R, 0, N, r + 1);
// Find the total segments not
// intersecting with the current
// segment
let cnt = x + y;
// Store the count of segments
// that intersect with the
// ith segment
cnt = N - cnt - 1;
// Update the value of count
count = Math.max(count, cnt);
}
// Return the resultant count
return count;
}
// Driver Code
let arr = [ [ 1, 6 ], [ 5, 5 ], [ 2, 3 ] ];
let N = arr.length;
document.write(maximumLetersections(arr, N));
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sunidhichandra27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA