Eliminaciones mínimas requeridas para hacer cualquier intervalo igual a la unión del Conjunto dado

Dado un conjunto S de tamaño N ( 1 ≤ N ≤ 1e5 ) que consta de intervalos, la tarea es encontrar los intervalos mínimos necesarios para ser eliminados del conjunto de modo que cualquiera de los intervalos restantes sea igual a la unión de este conjunto.

Ejemplos: 
 

Entrada: S = {[1, 3], [4, 12], [5, 8], [13, 20]}
Salida: 2
Explicación:
Eliminar los intervalos [1, 3] y [13, 20] modifica el establecer en { [4, 12], [5, 8]}. El intervalo [4, 12] es la unión del conjunto.

Entrada: S = {[1, 2], [1, 10], [4, 8], [3, 7]}
Salida: 0
Explicación:
Unión del conjunto dado = {[1, 10]}, que es ya presente en el conjunto. Por lo tanto, no se requieren mudanzas.

Planteamiento: El problema se puede resolver con base en la siguiente observación:

Observación: Para que cualquier intervalo sea igual a la unión del conjunto, el conjunto debe contener un intervalo [L, R] tal que todos los intervalos restantes tengan su límite izquierdo mayor que igual a L y el límite derecho menor que igual a R .

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

1. Recorre el conjunto dado de intervalos.
2. Para cada intervalo en el conjunto, encuentre todos los intervalos que tienen su límite izquierdo mayor o igual que su límite izquierdo y que tienen su límite derecho menor o igual que su límite derecho. Almacene el conteo de tales intervalos en una variable, digamos Count .
3. Encuentre el valor mínimo de todos los valores N – Count (ya que N – Count daría el número de intervalos eliminados) para cada intervalo.
4. Imprime el valor mínimo obtenido como respuesta requerida.

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count minimum number of removals
// required to make an interval equal to the
// union of the given Set
int findMinDeletions(vector<pair<int, int> >& v,
                     int n)
{
    // Stores the minimum number of removals
    int minDel = INT_MAX;
 
    // Traverse the Set
    for (int i = 0; i < n; i++) {
 
        // Left Boundary
        int L = v[i].first;
 
        // Right Boundary
        int R = v[i].second;
 
        // Stores count of intervals
        // lying within current interval
        int Count = 0;
 
        // Traverse over all remaining intervals
        for (int j = 0; j < n; j++) {
 
            // Check if interval lies within
            // the current interval
            if (v[j].first >= L && v[j].second <= R) {
 
                // Increase count
                Count += 1;
            }
        }
 
        // Update minimum removals required
        minDel = min(minDel, n - Count);
    }
    return minDel;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > v;
    v.push_back({ 1, 3 });
    v.push_back({ 4, 12 });
    v.push_back({ 5, 8 });
    v.push_back({ 13, 20 });
 
    int N = v.size();
 
    // Returns the minimum removals
    cout << findMinDeletions(v, N);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
class GFG{
 
// Function to count minimum number of removals
// required to make an interval equal to the
// union of the given Set
static int findMinDeletions(int [][]v,
                            int n)
{
   
    // Stores the minimum number of removals
    int minDel = Integer.MAX_VALUE;
 
    // Traverse the Set
    for (int i = 0; i < n; i++)
    {
 
        // Left Boundary
        int L = v[i][0];
 
        // Right Boundary
        int R = v[i][1];
 
        // Stores count of intervals
        // lying within current interval
        int Count = 0;
 
        // Traverse over all remaining intervals
        for (int j = 0; j < n; j++)
        {
 
            // Check if interval lies within
            // the current interval
            if (v[j][0] >= L && v[j][1] <= R)
            {
 
                // Increase count
                Count += 1;
            }
        }
 
        // Update minimum removals required
        minDel = Math.min(minDel, n - Count);
    }
    return minDel;
}
 
// Driver Code
public static void main(String[] args)
{
    int [][]v = {{ 1, 3 },
                 { 4, 12 },
                 { 5, 8 },
                 { 13, 20 }};
 
    int N = v.length;
 
    // Returns the minimum removals
    System.out.print(findMinDeletions(v, N));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the above approach
 
 
# Function to count minimum number of removals
# required to make an interval equal to the
# union of the given Set
def findMinDeletions(v, n):
   
    # Stores the minimum number of removals
    minDel = 10**18
 
    # Traverse the Set
    for i in range(n):
 
        # Left Boundary
        L = v[i][0]
 
        # Right Boundary
        R = v[i][1]
 
        # Stores count of intervals
        # lying within current interval
        Count = 0
 
        # Traverse over all remaining intervals
        for j in range(n):
 
            # Check if interval lies within
            # the current interval
            if (v[j][1] >= L and v[j][0] <= R):
                 
                # Increase count
                Count += 1
 
        # Update minimum removals required
        minDel = min(minDel, n - Count)
    return minDel
 
# Driver Code
if __name__ == '__main__':
    v = []
    v.append([1, 3])
    v.append([4, 12])
    v.append([5, 8])
    v.append([13, 2])
 
    N = len(v)
 
    # Returns the minimum removals
    print (findMinDeletions(v, N))
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
 
public class GFG{
 
// Function to count minimum number of removals
// required to make an interval equal to the
// union of the given Set
static int findMinDeletions(int [,]v,
                            int n)
{
   
    // Stores the minimum number of removals
    int minDel = int.MaxValue;
 
    // Traverse the Set
    for (int i = 0; i < n; i++)
    {
 
        // Left Boundary
        int L = v[i,0];
 
        // Right Boundary
        int R = v[i,1];
 
        // Stores count of intervals
        // lying within current interval
        int Count = 0;
 
        // Traverse over all remaining intervals
        for (int j = 0; j < n; j++)
        {
 
            // Check if interval lies within
            // the current interval
            if (v[j,0] >= L && v[j,1] <= R)
            {
 
                // Increase count
                Count += 1;
            }
        }
 
        // Update minimum removals required
        minDel = Math.Min(minDel, n - Count);
    }
    return minDel;
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]v = {{ 1, 3 },
                 { 4, 12 },
                 { 5, 8 },
                 { 13, 20 }};
 
    int N = v.GetLength(0);
 
    // Returns the minimum removals
    Console.Write(findMinDeletions(v, N));
}
}
 
  
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to implement
// the above approach
 
// Function to count minimum number of removals
// required to make an interval equal to the
// union of the given Set
function findMinDeletions(v, n)
{
    
    // Stores the minimum number of removals
    let minDel = Number.MAX_VALUE;
  
    // Traverse the Set
    for (let i = 0; i < n; i++)
    {
  
        // Left Boundary
        let L = v[i][0];
  
        // Right Boundary
        let R = v[i][1];
  
        // Stores count of intervals
        // lying within current interval
        let Count = 0;
  
        // Traverse over all remaining intervals
        for (let j = 0; j < n; j++)
        {
  
            // Check if interval lies within
            // the current interval
            if (v[j][0] >= L && v[j][1] <= R)
            {
  
                // Increase count
                Count += 1;
            }
        }
  
        // Update minimum removals required
        minDel = Math.min(minDel, n - Count);
    }
    return minDel;
}
 
// Driver Code
 
    let v = [[ 1, 3 ],
                 [ 4, 12 ],
                 [ 5, 8 ],
                 [ 13, 20 ]];
  
    let N = v.length;
  
    // Returns the minimum removals
    document.write(findMinDeletions(v, N));
  
 // This code is contributed by souravghosh0416.
</script>

2

Tiempo Complejidad: O(N ² )
Espacio auxiliar: O(1)