Minimice los segmentos que deben eliminarse de modo que al menos un segmento se cruce con todos los segmentos restantes

Dada una array arr[] que consta de N pares [L, R] , donde L y R denotan los índices inicial y final de un segmento, la tarea es encontrar la cantidad mínima de segmentos que deben eliminarse de la array de modo que el la array restante contiene al menos un segmento que se cruza con todos los demás segmentos presentes en la array.

Ejemplos:

Entrada: arr[] = {{1, 2}, {5, 6}, {6, 7}, {7, 10}, {8, 9}}
Salida: 2
Explicación: Eliminar los segmentos {1, 2} y {5, 6}. Por lo tanto, la array restante contiene el segmento {7, 10} que se cruza con todos los demás segmentos.

Entrada: a[] = {{1, 2}, {2, 3}, {1, 5}, {4, 5}}
Salida: 0
Explicación: El segmento {1, 5} ya se cruza con todos los demás segmentos restantes . Por lo tanto, no es necesario eliminar ningún segmento.

Enfoque: La máxima respuesta posible es (N – 1) , ya que después de eliminar (N – 1) segmentos de arr[] , solo quedará un segmento. Este segmento se cruza consigo mismo. Para lograr la respuesta mínima, la idea es iterar a través de todos los segmentos y, para cada segmento, verificar la cantidad de segmentos que no intersecan con él.

Dos segmentos [f ₁ , s ₁ ] y [f ₂ , s ₂ ] se intersecan solo cuando max(f ₁ , f ₂ ) ≤ min(s ₁ , s ₂ ) . 
Por lo tanto, si [f ₁ , s ₁ ] no se cruza con [f ₂ , s ₂ ] , entonces solo hay dos posibilidades:

1. s ₁ < f ₂  es decir, el segmento 1 termina antes del inicio del segmento 2
2. f ₁ > s ₂   , es decir, el segmento 1 comienza después del final del segmento 2.

Siga los pasos a continuación para resolver el problema:

• Recorra la array arr[] y almacene el punto de inicio y el punto final de cada segmento en startPoints[] y endPoints[] respectivamente.
• Ordene las arrays , startPoints[] y endPoints[] en orden creciente.
• Inicialice ans como (N – 1) para almacenar el número mínimo de eliminaciones requeridas.
• Recorra nuevamente la array, arr[] y para cada segmento:
  • Almacene el número de segmentos que satisfacen la primera y la segunda condición de no intersección en leftDelete y rightDelete respectivamente.
  • Si leftDelete + rightDelete es menor que ans , establezca ans en leftDelete + rightDelete .
• Después de los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of segments required to be deleted
void minSegments(pair<int, int> segments[],
                 int n)
{
    // Stores the start and end points
    int startPoints[n], endPoints[n];
 
    // Traverse segments and fill the
    // startPoints and endPoints
    for (int i = 0; i < n; i++) {
        startPoints[i] = segments[i].first;
        endPoints[i] = segments[i].second;
    }
 
    // Sort the startPoints
    sort(startPoints, startPoints + n);
 
    // Sort the startPoints
    sort(endPoints, endPoints + n);
 
    // Store the minimum number of
    // deletions required and
    // initialize with (N - 1)
    int ans = n - 1;
 
    // Traverse the array segments[]
    for (int i = 0; i < n; i++) {
 
        // Store the starting point
        int f = segments[i].first;
 
        // Store the ending point
        int s = segments[i].second;
 
        // Store the number of segments
        // satisfying the first condition
        // of non-intersection
        int leftDelete
            = lower_bound(endPoints,
                          endPoints + n, f)
              - endPoints;
 
        // Store the number of segments
        // satisfying the second condition
        // of non-intersection
        int rightDelete = max(
            0, n - (int)(upper_bound(startPoints,
                                     startPoints + n, s)
                         - startPoints));
 
        // Update answer
        ans = min(ans,
                  leftDelete
                      + rightDelete);
    }
 
    // Print the answer
    cout << ans;
}
 
// Driver Code
int main()
{
    pair<int, int> arr[] = {
        { 1, 2 }, { 5, 6 },
        { 6, 7 }, { 7, 10 }, { 8, 9 }
    };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    minSegments(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Pair class
static class Pair
{
    int first;
    int second;
 
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
public static int lower_bound(int arr[], int key)
{
    int l = -1, r = arr.length;
    while (l + 1 < r)
    {
        int m = (l + r) >>> 1;
        if (arr[m] >= key)
            r = m;
        else
            l = m;
    }
    return r;
}
 
public static int upper_bound(int arr[], int key)
{
    int l = -1, r = arr.length;
    while (l + 1 < r)
    {
        int m = (l + r) >>> 1;
        if (arr[m] <= key)
            l = m;
        else
            r = m;
    }
    return l + 1;
}
 
// Function to find the minimum number
// of segments required to be deleted
static void minSegments(Pair segments[], int n)
{
     
    // Stores the start and end points
    int startPoints[] = new int[n];
    int endPoints[] = new int[n];
 
    // Traverse segments and fill the
    // startPoints and endPoints
    for(int i = 0; i < n; i++)
    {
        startPoints[i] = segments[i].first;
        endPoints[i] = segments[i].second;
    }
 
    // Sort the startPoints
    Arrays.sort(startPoints);
 
    // Sort the startPoints
    Arrays.sort(endPoints);
 
    // Store the minimum number of
    // deletions required and
    // initialize with (N - 1)
    int ans = n - 1;
 
    // Traverse the array segments[]
    for(int i = 0; i < n; i++)
    {
         
        // Store the starting point
        int f = segments[i].first;
 
        // Store the ending point
        int s = segments[i].second;
 
        // Store the number of segments
        // satisfying the first condition
        // of non-intersection
        int leftDelete = lower_bound(endPoints, f);
 
        // Store the number of segments
        // satisfying the second condition
        // of non-intersection
        int rightDelete = Math.max(
            0, n - (int)(upper_bound(startPoints, s)));
 
        // Update answer
        ans = Math.min(ans, leftDelete + rightDelete);
    }
 
    // Print the answer
    System.out.println(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    Pair arr[] = { new Pair(1, 2), new Pair(5, 6),
                   new Pair(6, 7), new Pair(7, 10),
                   new Pair(8, 9) };
    int N = arr.length;
     
    // Function Call
    minSegments(arr, N);
}
}
 
// This code is contributed by Kingash

# Python3 program for the above approach
 
from bisect import bisect_left,bisect_right
# Function to find the minimum number
# of segments required to be deleted
def minSegments(segments, n):
    # Stores the start and end points
    startPoints = [0 for i in range(n)]
    endPoints = [0 for i in range(n)]
 
    # Traverse segments and fill the
    # startPoints and endPoints
    for i in range(n):
        startPoints[i] = segments[i][0]
        endPoints[i] = segments[i][1]
 
    # Sort the startPoints
    startPoints.sort(reverse = False)
 
    # Sort the startPoints
    endPoints.sort(reverse= False)
 
    # Store the minimum number of
    # deletions required and
    # initialize with (N - 1)
    ans = n - 1
 
    # Traverse the array segments[]
    for i in range(n):
        # Store the starting point
        f = segments[i][0]
 
        # Store the ending point
        s = segments[i][1]
 
        # Store the number of segments
        # satisfying the first condition
        # of non-intersection
        leftDelete = bisect_left(endPoints, f)
 
        # Store the number of segments
        # satisfying the second condition
        # of non-intersection
        rightDelete = max(0, n - bisect_right(startPoints,s))
 
        # Update answer
        ans = min(ans, leftDelete + rightDelete)
 
    # Print the answer
    print(ans)
 
# Driver Code
if __name__ == '__main__':
    arr = [[1, 2],[5, 6], [6, 7],[7, 10],[8, 9]]
    N = len(arr)
 
    # Function Call
    minSegments(arr, N)
 
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // Pair class
    class Pair {
        public int first;
        public int second;
        public Pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    public static int lower_bound(int[] arr, int key)
    {
        int l = -1, r = arr.Length;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (arr[m] >= key)
                r = m;
            else
                l = m;
        }
        return r;
    }
 
    public static int upper_bound(int[] arr, int key)
    {
        int l = -1, r = arr.Length;
        while (l + 1 < r) {
            int m = (l + r) >> 1;
            if (arr[m] <= key)
                l = m;
            else
                r = m;
        }
        return l + 1;
    }
 
    static void minSegments(Pair[] segments, int n)
    {
        // Stores the start and end points
        int[] startPoints = new int[n];
        int[] endPoints = new int[n];
 
        // Traverse segments and fill the
        // startPoints and endPoints
        for (int i = 0; i < n; i++) {
            startPoints[i] = segments[i].first;
            endPoints[i] = segments[i].second;
        }
 
        // Sort the startPoints
        Array.Sort(startPoints);
 
        // Sort the startPoints
        Array.Sort(endPoints);
 
        // Store the minimum number of
        // deletions required and
        // initialize with (N - 1)
        int ans = n - 1;
 
        // Traverse the array segments[]
        for (int i = 0; i < n; i++) {
 
            // Store the starting point
            int f = segments[i].first;
 
            // Store the ending point
            int s = segments[i].second;
 
            // Store the number of segments
            // satisfying the first condition
            // of non-intersection
            int leftDelete = lower_bound(endPoints, f);
 
            // Store the number of segments
            // satisfying the second condition
            // of non-intersection
            int rightDelete = Math.Max(
                0, n - (int)(upper_bound(startPoints, s)));
 
            // Update answer
            ans = Math.Min(ans, leftDelete + rightDelete);
        }
 
        // Print the answer
        Console.WriteLine(ans);
    }
 
    static public void Main()
    {
 
        // Code
        Pair[] arr = { new Pair(1, 2), new Pair(5, 6),
                       new Pair(6, 7), new Pair(7, 10),
                       new Pair(8, 9) };
 
        int N = arr.Length;
        minSegments(arr, N);
    }
}
 
// This code is contributed by lokesh (lokeshmvs21).

2

Complejidad de tiempo: O(N*(log N ² ))
Espacio auxiliar: O(N)