Número de formas de elegir K segmentos de línea de intersección en el eje X

Dada una array arr[] de segmentos de línea en el eje x y un número entero K , la tarea es calcular el número de formas de elegir los K segmentos de línea para que se crucen en cualquier punto. Como la respuesta puede ser grande, imprímela en módulo 10^9+7.

Ejemplos:  

Entrada: arr[] = [[1, 3], [4, 5], [5, 7]], K = 2 
Salida: 2 
Explicación: 
La primera forma de elegir [1, 3], [4, 5] y la segunda forma es [1, 3], [5, 7]. Dado que la intersección de [4, 5], [5, 7] no es cero y, por lo tanto, no se puede incluir en la respuesta.

Entrada: [[3, 7], [1, 4], [6, 9], [8, 13], [9, 11]], K = 1 
Salida: 0 
Explicación: 
Dado que solo estamos buscando una sola línea segmento, pero para cada segmento de línea individual, la intersección siempre no está vacía. 

Planteamiento:
Para resolver el problema mencionado anteriormente, intentaremos encontrar el número de casos impares, es decir, aquellos casos cuya intersección no está vacía. Así que claramente nuestra respuesta será Caso Total – Caso Impar.  
Para calcular el número total de casos, se sigue el siguiente enfoque:  

• Los casos totales que son posibles son “n elige k” o ⁿ C _k
• Precalculamos el inverso y el factorial de los números requeridos para calcular ⁿ C _k
• en tiempo O(1)
• El segmento de línea K se interseca como si min(R1, R2, .., R{k-1}) >= Li donde se está considerando el segmento de línea [Li, Ri]. Mantener un multiset, para mantener el orden. En primer lugar, ordene los segmentos en orden creciente de Li. Si Li son iguales, entonces el segmento con Ri más pequeño viene primero.

Para cada segmento de línea [Li, Ri], se sigue el siguiente enfoque para encontrar el número de casos impares.  

• Si bien multiset no está vacío y las líneas no se cruzan, elimine la línea con el Ri más pequeño de multiset y verifique nuevamente.
• Número de formas violatorias usando este segmento [Li, Ri] son ^​​p C _k-1
• donde p = tamaño_de_multiconjunto.
• Inserte el punto final de este segmento de línea en el conjunto múltiple.

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

// C++ program to find Number of ways
// to choose K intersecting
// line segments on X-axis
 
#include <bits/stdc++.h>
using namespace std;
 
const long long mod = 1000000007;
const int MAXN = 1001;
long long factorial[MAXN], inverse[MAXN];
 
// Function to find (a^b)%mod in log b
long long power(long long a, long long b)
{
    long long res = 1;
 
    // Till power becomes 0
    while (b > 0) {
 
        // If power is odd
        if (b % 2 == 1) {
            res = (res * a) % mod;
        }
        // Multiply base
        a = (a * a) % mod;
 
        // Divide power by 1
        b >>= 1;
    }
 
    return res;
}
 
// Function to find nCk
long long nCk(int n, int k)
{
    // Base case
    if (k < 0 || k > n) {
        return 0;
    }
 
    // Apply formula to find nCk
    long long ans = factorial[n];
    ans = (ans * inverse[n - k]) % mod;
    ans = (ans * inverse[k]) % mod;
 
    return ans;
}
 
// Function to find the number of ways
void numberOfWays(vector<pair<int, int> > lines, int K,
                  int N)
{
 
    // sort the given lines
    sort(lines.begin(), lines.end());
 
    // Find the number of total case
    long long total_case = nCk(N, K);
 
    // Declare a multiset
    multiset<int> m;
 
    // loop till N
    for (int i = 0; i < N; i++)
    {
 
        // Check if smallest element is
        // smaller than lines[i]
        while (!m.empty()
               && (*m.begin() < lines[i].first)) {
 
            // Erase first element
            m.erase(m.begin());
        }
        // Exclude the odd cases
        total_case -= nCk(m.size(), K - 1);
 
        // Modulus operation
        total_case += mod;
        total_case %= mod;
 
        // Insert into multiset
        m.insert(lines[i].second);
    }
 
    cout << total_case << endl;
}
 
// Function to precompute
// factorial and inverse
void preCompute()
{
    long long fact = 1;
 
    factorial[0] = 1;
    inverse[0] = 1;
 
    // Pre-compute factorial and inverse
    for (int i = 1; i < MAXN; i++) {
 
        fact = (fact * i) % mod;
        factorial[i] = fact;
        inverse[i] = power(factorial[i], mod - 2);
    }
}
 
// Driver code
int main()
{
 
    int N = 3, K = 2;
    vector<pair<int, int> > lines;
 
    // Function to pre-compute
    // factorial and inverse
    preCompute();
 
    lines.push_back({ 1, 3 });
    lines.push_back({ 4, 5 });
    lines.push_back({ 5, 7 });
 
    numberOfWays(lines, K, N);
 
    return 0;
}

// Java program to find Number of ways
// to choose K intersecting line
// segments on X-axis
import java.util.*;
import java.lang.*;
 
class GFG {
 
    static long mod = 1000000007;
    static int MAXN = 1001;
    static long factorial[] = new long[MAXN],
                inverse[] = new long[MAXN];
 
    // Function to find (a^b)%mod in log b
    static long power(long a, long b)
    {
        long res = 1;
 
        // Till power becomes 0
        while (b > 0) {
 
            // If power is odd
            if (b % 2 == 1) {
                res = (res * a) % mod;
            }
 
            // Multiply base
            a = (a * a) % mod;
 
            // Divide power by 1
            b >>= 1;
        }
        return res;
    }
 
    // Function to find nCk
    static long nCk(int n, int k)
    {
 
        // Base case
        if (k < 0 || k > n) {
            return 0;
        }
 
        // Apply formula to find nCk
        long ans = factorial[n];
        ans = (ans * inverse[n - k]) % mod;
        ans = (ans * inverse[k]) % mod;
 
        return ans;
    }
 
    // Function to find the number of ways
    static void numberOfWays(ArrayList<int[]> lines, int K,
                             int N)
    {
 
        // sort the given lines
        Collections.sort(lines, (a, b) -> a[0] - b[0]);
 
        // Find the number of total case
        long total_case = nCk(N, K);
 
        // Declare a multiset
        PriorityQueue<Integer> m = new PriorityQueue<>();
 
        // Loop till N
        for (int i = 0; i < N; i++) {
 
            // Check if smallest element is
            // smaller than lines[i]
            while (!m.isEmpty()
                   && (m.peek() < lines.get(i)[0])) {
 
                // Erase first element
                m.poll();
            }
 
            // Exclude the odd cases
            total_case -= nCk(m.size(), K - 1);
 
            // Modulus operation
            total_case += mod;
            total_case %= mod;
 
            // Insert into multiset
            m.add(lines.get(i)[1]);
        }
        System.out.println(total_case);
    }
 
    // Function to precompute
    // factorial and inverse
    static void preCompute()
    {
        long fact = 1;
 
        factorial[0] = 1;
        inverse[0] = 1;
 
        // Pre-compute factorial and inverse
        for (int i = 1; i < MAXN; i++) {
            fact = (fact * i) % mod;
            factorial[i] = fact;
 
            inverse[i] = power(factorial[i], mod - 2);
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 3, K = 2;
        ArrayList<int[]> lines = new ArrayList<>();
 
        // Function to pre-compute
        // factorial and inverse
        preCompute();
 
        lines.add(new int[] { 1, 3 });
        lines.add(new int[] { 4, 5 });
        lines.add(new int[] { 5, 7 });
 
        numberOfWays(lines, K, N);
    }
}
 
// This code is contributed by offbeat

# Python3 program to find Number of ways
# to choose K ersecting
# line segments on X-axis
 
import heapq as hq
 
mod = 1000000007
MAXN = 1001
factorial=[1]*MAXN; inverse=[1]*MAXN
 
# Function to find (a^b)%mod in log b
def power(a, b):
    res = 1
 
    # Till power becomes 0
    while (b > 0) :
 
        # If power is odd
        if (b % 2 == 1) :
            res = (res * a) % mod
         
        # Multiply base
        a = (a * a) % mod
 
        # Divide power by 1
        b >>= 1
     
 
    return res
 
 
# Function to find nCk
def nCk(n, k):
    # Base case
    if (k < 0 or k > n) :
        return 0
     
 
    # Apply formula to find nCk
    ans = factorial[n]
    ans = (ans * inverse[n - k]) % mod
    ans = (ans * inverse[k]) % mod
 
    return ans
 
 
# Function to find the number of ways
def numberOfWays(lines, K, N):
 
    # sort the given lines
    lines.sort()
 
    # Find the number of total case
    total_case = nCk(N, K)
 
    # Declare a heap
    m=[]
 
    # loop till N
    for i in range(N):
 
        # Check if smallest element is
        # smaller than lines[i]
        while (m and m[0] < lines[i][0]):
 
            # Erase first element
            hq.heappop(m)
         
        # Exclude the odd cases
        total_case -= nCk(len(m), K - 1)
 
        # Modulus operation
        total_case += mod
        total_case %= mod
 
        # Insert into heap
        hq.heappush(m,lines[i][1])
     
 
    print(total_case)
 
 
# Function to precompute
# factorial and inverse
def preCompute():
    global factorial
    fact = 1
 
    factorial[0] = 1
    inverse[0] = 1
 
    # Pre-compute factorial and inverse
    for i in range(1,MAXN) :
 
        fact = (fact * i) % mod
        factorial[i] = fact
        inverse[i] = power(factorial[i], mod - 2)
     
 
 
# Driver code
if __name__ == '__main__':
 
    N = 3; K = 2
    lines=[]
 
    # Function to pre-compute
    # factorial and inverse
    preCompute()
 
    lines.append((1, 3))
    lines.append((4, 5))
    lines.append((5, 7))
 
    numberOfWays(lines, K, N)

2

Complejidad de tiempo: O(MAXN * log(MAXN) + N * log(N)).
Espacio Auxiliar: O(MAXN + N).