Número mínimo de pares requeridos para ser seleccionados para cubrir un rango dado

Dada una array arr[] que consta de N pares y un entero positivo K , la tarea es seleccionar el número mínimo de pares que cubra todo el rango [0, K] . Si no es posible cubrir el rango [0, K] , imprima -1 .

Ejemplos:

Entrada: arr[] = {{0, 3}, {2, 5}, {5, 6}, {6, 8}, {6, 10}}, K = 10
Salida: 4
Explicación: Uno de los valores óptimos formas es seleccionar los rangos {{0, 3}, {2, 5}, {5, 6}, {6, 10}} que cubre todo el rango [0, 10].

Entrada: arr[] = {{0, 4}, {1, 5}, {5, 6}, {8, 10}}, N = 10
Salida: -1

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subconjuntos posibles y verificar para cada subconjunto si cubre el rango completo o no. 

Complejidad temporal: O(2 ^N × N) 
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar ordenando la array en orden creciente sobre la base del elemento izquierdo y para pares con elementos izquierdos iguales, ordenando los elementos en orden decreciente de su elemento derecho. Ahora, elige los pares de manera óptima. 

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

• Ordene el vector de pares arr[] en orden creciente del elemento izquierdo y si los elementos izquierdos son iguales, luego ordene la array en orden decreciente del elemento derecho del par.
• Compruebe si arr[0][0] != 0 luego imprima -1 .
• Inicialice una variable, digamos R como arr[0][1] que almacena el límite derecho del rango y ans como 1 que almacena el número de rangos necesarios para cubrir el rango [0, K] .
• Iterar en el rango [0, N-1] usando la variable i y realizar los siguientes pasos:
  • Si R == K , termina el bucle.
  • Inicialice una variable, digamos maxr como R , que almacena el límite derecho máximo donde el límite izquierdo ≤ R .
  • Iterar en el rango [i+1, N-1] usando la variable j y realizar los siguientes pasos:
    • Si arr[j][0] ≤ R , modifique el valor de maxr como max(maxr, arr[j][1]) .
  • Modifique el valor de i como j-1 y el valor de R como maxr e incremente el valor de ans en 1.
• Si R no es igual a K , imprima -1 .
• De lo contrario, imprima el valor de ans .

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 sort the elements in
// increasing order of left element and
// sort pairs with equal left element in
// decreasing order of right element
static bool cmp(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first) {
        return a.second > b.second;
    }
    else {
        return b.first > a.first;
    }
}
 
// Function to select minimum number of pairs
// such that it covers the entire range [0, K]
int MinimumPairs(vector<pair<int, int> > arr, int K)
{
    int N = arr.size();
 
    // Sort the array using comparator
    sort(arr.begin(), arr.end(), cmp);
 
    // If the start element
    // is not equal to 0
    if (arr[0].first != 0) {
        return -1;
    }
 
    // Stores the minimum
    // number of pairs required
    int ans = 1;
 
    // Stores the right bound of the range
    int R = arr[0].second;
 
    // Iterate in the range[0, N-1]
    for (int i = 0; i < N; i++) {
        if (R == K) {
            break;
        }
 
        // Stores the maximum right bound
        // where left bound ≤ R
        int maxr = R;
 
        int j;
 
        // Iterate in the range [i+1, N-1]
        for (j = i + 1; j < N; j++) {
 
            // If the starting point of j-th
            // element is less than equal to R
            if (arr[j].first <= R) {
 
                maxr = max(maxr, arr[j].second);
            }
 
            // Otherwise
            else {
                break;
            }
        }
 
        i = j - 1;
        R = maxr;
        ans++;
    }
 
    // If the right bound
    // is not equal to K
    if (R != K) {
        return -1;
    }
 
    // Otherwise
    else {
        return ans;
    }
}
 
// Driver Code
int main()
{
    // Given Input
    int K = 4;
    vector<pair<int, int> > arr{ { 0, 6 } };
 
    // Function Call
    cout << MinimumPairs(arr, K);
}

// Java Program for above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
// User defined Pair class
class Pair
{
    int x;
    int y;
 
    // Constructor
    public Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
// class to sort the elements in
// increasing order of left element and
// sort pairs with equal left element in
// decreasing order of right element
class cmp implements Comparator<Pair>
{
 
    public int compare(Pair p1, Pair p2)
    {
        if (p1.x == p2.x)
        {
            return p1.y - p2.y;
        }
        else
        {
            return p2.x - p1.x;
        }
    }
}
 
class GFG
{
    // Function to select minimum number of pairs
    // such that it covers the entire range [0, K]
    public static int MinimumPairs(Pair arr[], int K)
    {
        int N = arr.length;
        // Sort the array using comparator
        Arrays.sort(arr, new cmp());
 
        // If the start element
        // is not equal to 0
        if (arr[0].x != 0)
        {
            return -1;
        }
 
        // Stores the minimum
        // number of pairs required
        int ans = 1;
 
        // Stores the right bound of the range
        int R = arr[0].y;
 
        // Iterate in the range[0, N-1]
        for (int i = 0; i < N; i++)
        {
            if (R == K)
            {
                break;
            }
 
            // Stores the maximum right bound
            // where left bound is less than equal to R
            int maxr = R;
            int j;
 
            // Iterate in the range [i+1, N-1]
            for (j = i + 1; j < N; j++)
            {
 
                // If the starting point of j-th
                // element is less than equal to R
                if (arr[j].x <= R)
                {
 
                    maxr = Math.max(maxr, arr[j].y);
                }
 
                // Otherwise
                else
                {
                    break;
                }
            }
 
            i = j - 1;
            R = maxr;
            ans++;
        }
 
        // If the right bound
        // is not equal to K
        if (R != K)
        {
            return -1;
        }
 
        // Otherwise
        else
        {
            return ans;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int K = 4;
        int n = 1; // length of array
        Pair arr[] = new Pair[n];
        arr[0] = new Pair(0, 6);
 
        System.out.println(MinimumPairs(arr, K));
    }
}
 
// This code is contributed by rj13to.

# Python3 program for the above approach
 
# Function to select minimum number of pairs
# such that it covers the entire range [0, K]
def MinimumPairs(arr, K):
     
    N = len(arr)
 
    # Sort the array using comparator
    arr.sort()
 
    # If the start element
    # is not equal to 0
    if (arr[0][0] != 0):
        return -1
 
    # Stores the minimum
    # number of pairs required
    ans = 1
 
    # Stores the right bound of the range
    R = arr[0][1]
 
    # Iterate in the range[0, N-1]
    for i in range(N):
        if (R == K):
            break
 
        # Stores the maximum right bound
        # where left bound ≤ R
        maxr = R
 
        j = 0
 
        # Iterate in the range [i+1, N-1]
        for j in range(i + 1, N, 1):
             
            # If the starting point of j-th
            # element is less than equal to R
            if (arr[j][0] <= R):
                maxr = max(maxr, arr[j][1])
 
            # Otherwise
            else:
                break
 
        i = j - 1
        R = maxr
        ans += 1
 
    # If the right bound
    # is not equal to K
    if (R != K):
        return -1
 
    # Otherwise
    else:
        return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    K = 4
    arr = [ [ 0, 6 ] ]
 
    # Function Call
    print(MinimumPairs(arr, K))
 
# This code is contributed by bgangwar59

<script>
 
// JavaScript program for the above approach
 
// Function to select minimum number of pairs
// such that it covers the entire range [0, K]
function MinimumPairs(arr, K){
     
    let N = arr.length
 
    // Sort the array using comparator
    arr.sort((a,b)=>a-b)
 
    // If the start element
    // is not equal to 0
    if (arr[0][0] != 0)
        return -1
 
    // Stores the minimum
    // number of pairs required
    let ans = 1
 
    // Stores the right bound of the range
    let R = arr[0][1]
 
    // Iterate in the range[0, N-1]
    for(let i=0;i<N;i++){
        if(R == K)
            break
 
    //     // Stores the maximum right bound
    //     // where left bound ≤ R
        let maxr = R
 
        let j = 0
 
        // Iterate in the range [i+1, N-1]
        for(j=i+1;j<N;j++){
             
            // If the starting point of j-th
            // element is less than equal to R
            if (arr[j][0] <= R)
                maxr = Math.max(maxr, arr[j][1])
 
            // Otherwise
            else break
        }
 
        i = j - 1
        R = maxr
        ans += 1
 
    }
 
    // // If the right bound
    // // is not equal to K
    if(R != K)
        return -1
 
    // Otherwise
    else
        return ans
}
 
// Driver Code
     
// Given Input
let K = 4
let arr = [ [ 0, 6 ] ]
 
// Function Call
document.write(MinimumPairs(arr, K),"</br>")
 
// This code is contributed by shinjanpatra
 
 
</script>

-1

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)