Recuento de formas de seleccionar exactamente K rangos no disjuntos de N rangos dados

Dadas dos arrays L[] y R[] de tamaño N, y un número entero K, la tarea es encontrar el número de formas de seleccionar K rangos disjuntos exactos formados al tomar elementos presentes en el mismo índice de la array L[] y R[].

Ejemplos : 

Entrada: N = 7, K = 3, L[] = {1, 3, 4, 6, 1, 5, 8}, R[] = {7, 8, 5, 7, 3, 10, 9}
Salida : 9
Explicación: 
Las posibles formas de seleccionar K rangos son: 

1. Seleccione rangos {1, 7}, {3, 8} y {4, 5}
2. Seleccione rangos {1, 7}, {3, 8} y {6, 7}
3. Seleccione rangos {1, 7}, {3, 8} y {1, 3}
4. Seleccione rangos {1, 7}, {3, 8} y {5, 10}
5. Seleccione rangos {1, 7}, {4, 5} y {5, 10}
6. Seleccione rangos {1, 7}, {6, 7} y {5, 10}
7. Seleccione rangos {3, 8}, {4, 5} y {5, 10}
8. Seleccione rangos {3, 8}, {6, 7} y {5, 10}
9. Seleccione rangos {3, 8}, {5, 10} y {8, 9}

Entrada: N = 2, K = 2, L[] = {100, 200}, R[] ={ 201, 300}
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es seleccionar todos los pares K distintos posibles y verificar si son disjuntos para cada par de todos los rangos.

Complejidad temporal: O(N!)
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar comprobando para cada rango el número de rangos no disjuntos que se pueden usar con el rango actual. Siga los pasos a continuación para optimizar el enfoque anterior:

• Inicialice una variable, digamos, cnt para contar el número de rangos no disjuntos para cada rango actual.
• Inicialice un vector de pares , digamos preprocesado para almacenar todo el límite izquierdo como {L[i], 1} y el límite derecho como {R[i]+1, -1} de un rango.
• Iterar sobre el rango [0, N] , usando la variable i , y realizar los siguientes pasos:
  • Introduzca los pares {L[i], 1} y {R[i]+1, -1} en el vector preprocesado .
• Ordene el vector , preprocesado en orden no decreciente.
• Inicialice las variables, diga ans y cnt como 0 para almacenar la respuesta y almacenar el segmento que se cruza con el rango actual.
• Itere sobre el vector preprocesado usando la variable i y haga lo siguiente:
  • Si el segundo elemento del par es 1 y cnt >= K-1, entonces aumente la ^respuesta en cnt C _K-1 y actualice cnt a cnt+1.
  • De lo contrario, actualice el cnt como cnt+1.
• Finalmente, después de completar los pasos anteriores, imprima el 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;
 
// Utility function to calculate nCr
int nCr(int n, int r, int* f)
{
    return f[n] / f[r] * f[n - r];
}
 
// Function to calculate number of ways
// to choose K ranges such that no two of
// them are disjoint.
int NumberOfWaysToChooseKRanges(int L[], int R[],
                                int N, int K)
{
    // Stores the factorials
    int f[N + 1];
    f[0] = 1;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
        f[i] = f[i - 1] * i;
    }
 
    // Preprocessing the ranges into
    // new vector
    vector<pair<int, int> > preprocessed;
 
    // Traverse the given ranges
    for (int i = 0; i < N; i++) {
        preprocessed.push_back(make_pair(L[i], 1));
        preprocessed.push_back(make_pair(R[i] + 1, -1));
    }
 
    // Sorting the preprocessed vector
    sort(preprocessed.begin(), preprocessed.end());
 
    // Stores the result
    int ans = 0;
 
    // Stores the count of non-disjoint ranges
    int Cnt = 0;
 
    // Traverse the proeprocesse vector of pairs
    for (int i = 0; i < preprocessed.size(); i++) {
 
        // If current point is a left boundary
        if (preprocessed[i].second == 1) {
            if (Cnt >= K - 1) {
                // Update the answer
                ans += nCr(Cnt, K - 1, f);
            }
 
            // Increment cnt by 1
            Cnt++;
        }
        else {
            // Decrement cnt by 1
            Cnt--;
        }
    }
 
    // Return the ans
    return ans;
}
 
// Driver Code
int main()
{
    // Given Input
    int N = 7, K = 3;
    int L[] = { 1, 3, 4, 6, 1, 5, 8 };
    int R[] = { 7, 8, 5, 7, 3, 10, 9 };
 
    // Function Call
    cout << NumberOfWaysToChooseKRanges(L, R, N, K);
    return 0;
}

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
   
static class pair
{
    int first, second;
      
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }  
}
  
// Utility function to calculate nCr
static int nCr(int n, int r, int f[])
{
    return f[n] / f[r] * f[n - r];
}
 
// Function to calculate number of ways
// to choose K ranges such that no two of
// them are disjoint.
static int NumberOfWaysToChooseKRanges(int L[], int R[],
                                int N, int K)
{
    // Stores the factorials
    int f[] = new int[N + 1];
    f[0] = 1;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
        f[i] = f[i - 1] * i;
    }
 
    // Preprocessing the ranges into
    // new vector
    Vector<pair > preprocessed = new Vector<pair >();
 
    // Traverse the given ranges
    for (int i = 0; i < N; i++) {
        preprocessed.add(new pair(L[i], 1));
        preprocessed.add(new pair(R[i] + 1, -1));
    }
 
    // Sorting the preprocessed vector
    Collections.sort(preprocessed, new Comparator<pair>() {
            @Override public int compare(pair p1, pair p2)
            {
                  if (p1.first != p2.first)
                    return (p1.first - p2.first);
                  return p1.second - p2.second;
            }
        });
 
    // Stores the result
    int ans = 0;
 
    // Stores the count of non-disjoint ranges
    int Cnt = 0;
 
    // Traverse the proeprocesse vector of pairs
    for (int i = 0; i < preprocessed.size(); i++) {
         
        // If current point is a left boundary
        if (preprocessed.elementAt(i).second == 1) {
            if (Cnt >= K - 1) {
                // Update the answer
                ans += nCr(Cnt, K - 1, f);
            }
 
            // Increment cnt by 1
            Cnt++;
        }
        else {
            // Decrement cnt by 1
            Cnt--;
        }
    }
 
    // Return the ans
    return ans;
}
 
// Driver Code
public static void main (String[] args) {
    // Given Input
    int N = 7, K = 3;
    int L[] = { 1, 3, 4, 6, 1, 5, 8 };
    int R[] = { 7, 8, 5, 7, 3, 10, 9 };
 
    // Function Call
    System.out.println(NumberOfWaysToChooseKRanges(L, R, N, K));
}
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
 
# Utility function to calculate nCr
def nCr(n, r, f):
     
    return f[n] // f[r] * f[n - r]
 
# Function to calculate number of ways
# to choose K ranges such that no two of
# them are disjoint.
def NumberOfWaysToChooseKRanges(L, R, N, K):
     
    # Stores the factorials
    f = [0 for i in range(N + 1)]
    f[0] = 1
 
    # Iterate over the range [1, N]
    for i in range(1, N + 1, 1):
        f[i] = f[i - 1] * i
 
    # Preprocessing the ranges into
    # new vector
    preprocessed = []
 
    # Traverse the given ranges
    for i in range(N):
        preprocessed.append([L[i], 1])
        preprocessed.append([R[i] + 1, -1])
 
    # Sorting the preprocessed vector
    preprocessed.sort()
 
    # Stores the result
    ans = 0
 
    # Stores the count of non-disjoint ranges
    Cnt = 0
 
    # Traverse the proeprocesse vector of pairs
    for i in range(len(preprocessed)):
         
        # If current point is a left boundary
        if (preprocessed[i][1] == 1):
            if (Cnt >= K - 1):
                 
                # Update the answer
                ans += nCr(Cnt, K - 1, f)
 
            # Increment cnt by 1
            Cnt += 1
        else:
             
            # Decrement cnt by 1
            Cnt -= 1
 
    # Return the ans
    return ans
 
# Driver Code
if __name__ == '__main__':
     
    # Given Input
    N = 7
    K = 3
    L = [ 1, 3, 4, 6, 1, 5, 8 ]
    R = [ 7, 8, 5, 7, 3, 10, 9 ]
 
    # Function Call
    print(NumberOfWaysToChooseKRanges(L, R, N, K))
 
# This code is contributed by SURENDRA_GANGWAR

<script>
 
// JavaScript program for the above approach
 
// Utility function to calculate nCr
function nCr(n, r, f) {
    return f[n] / f[r] * f[n - r];
}
 
// Function to calculate number of ways
// to choose K ranges such that no two of
// them are disjoint.
function NumberOfWaysToChooseKRanges(L, R, N, K) {
    // Stores the factorials
    let f = new Array(N + 1);
    f[0] = 1;
 
    // Iterate over the range [1, N]
    for (let i = 1; i <= N; i++) {
        f[i] = f[i - 1] * i;
    }
 
    // Preprocessing the ranges into
    // new vector
    let preprocessed = [];
 
    // Traverse the given ranges
    for (let i = 0; i < N; i++) {
        preprocessed.push([L[i], 1]);
        preprocessed.push([R[i] + 1, -1]);
    }
 
    // Sorting the preprocessed vector
    preprocessed.sort((a, b) => {
        if (a[0] != b[0])
            return a[0] - b[0]
        return a[1] - b[1]
    });
 
    // Stores the result
    let ans = 0;
 
    // Stores the count of non-disjoint ranges
    let Cnt = 0;
 
    // Traverse the proeprocesse vector of pairs
    for (let i = 0; i < preprocessed.length; i++) {
 
        // If current point is a left boundary
        if (preprocessed[i][1] == 1) {
            console.log("Hello babe")
 
            if (Cnt >= K - 1) {
                // Update the answer
                ans += nCr(Cnt, K - 1, f);
            }
 
            // Increment cnt by 1
            Cnt++;
        }
        else {
            // Decrement cnt by 1
            Cnt--;
        }
    }
 
    // Return the ans
    return ans;
}
 
// Driver Code
 
// Given Input
let N = 7, K = 3;
let L = [1, 3, 4, 6, 1, 5, 8];
let R = [7, 8, 5, 7, 3, 10, 9];
 
// Function Call
document.write(NumberOfWaysToChooseKRanges(L, R, N, K));
 
</script>

9

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