Problema de selección de actividades con K personas

Dadas dos arrays S[] y E[] de tamaño N que indican la hora de inicio y cierre de las tiendas y un valor entero K que indica la cantidad de personas, la tarea es averiguar la cantidad máxima de tiendas que pueden visitar en total si visite cada tienda de manera óptima en función de las siguientes condiciones:

• Una tienda puede ser visitada por una sola persona
• Una persona no puede visitar otra tienda si su horario choca con él.

Ejemplos:

Entrada: S[] = {1, 8, 3, 2, 6}, E[] = {5, 10, 6, 5, 9}, K = 2
Salida: 4
Explicación: una posible solución puede ser que la primera persona visita las tiendas 1 y 5, mientras que la segunda persona visitará las tiendas 4 y 2.

Entrada: S[] = {1, 2, 3}, E[] = {3, 4, 5}, K = 2
Salida: 3
Explicación: Una posible solución puede ser que la primera persona visite la primera y la tercera tienda mientras que la segunda la persona visitará la segunda tienda. 

Enfoque: este problema se puede resolver utilizando la técnica codiciosa llamada selección y clasificación de actividades . En el problema de selección de actividades, solo una persona realiza la actividad, pero aquí hay K personas disponibles para una actividad. Para gestionar la disponibilidad de una persona se utiliza un multiset .

1. Inicialice una array a[] de pares y almacene el par {S[i], E[i]} para cada índice i .
2. Ordene la array a[] según la hora de finalización.
3. Inicialice un multiset st para almacenar las personas con la hora de finalización de la tienda que están visitando actualmente.
4. Inicialice una variable ans con 0 para almacenar el resultado final.
5. Atraviesa cada par de arreglos a[] ,
   1. Si una persona está disponible, es decir , a[i].primero es mayor o igual que la hora de finalización de cualquier persona en el conjunto múltiple st , entonces incremente el conteo en 1 y actualice la hora de finalización de ese elemento con la nueva a[i]. segundo _
   2. De lo contrario, continúe revisando los siguientes pares.
6. Finalmente, imprima el resultado como count .

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Comparator
bool compareBy(const pair<int, int>& a,
               const pair<int, int>& b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}
// Function to find maximum shops
// that can be visited by K persons
int maximumShops(int* opening, int* closing,
                 int n, int k)
{
    // Store opening and closing
    // time of shops
    pair<int, int> a[n];
 
    for (int i = 0; i < n; i++) {
        a[i].first = opening[i];
        a[i].second = closing[i];
    }
 
    // Sort the pair of array
    sort(a, a + n, compareBy);
 
    // Stores the result
    int count = 0;
 
    // Stores current number of persons visiting
    // some shop with their ending time
    multiset<int> st;
 
    for (int i = 0; i < n; i++) {
 
        // Check if current shop can be
        // assigned to a person who's
        // already visiting any other shop
        bool flag = false;
 
        if (!st.empty()) {
 
            auto it = st.upper_bound(a[i].first);
 
            if (it != st.begin()) {
                it--;
 
                // Checks if there is any person whose
                // closing time <= current shop opening
                // time
                if (*it <= a[i].first) {
 
                    // Erase previous shop visited by the
                    // person satisfying the condition
                    st.erase(it);
 
                    // Insert new closing time of current
                    // shop for the person satisfying ṭhe
                    // condition
                    st.insert(a[i].second);
 
                    // Increment the count by one
                    count++;
 
                    flag = true;
                }
            }
        }
 
        // In case if no person have closing
        // time <= current shop opening time
        // but there are some persons left
        if (st.size() < k && flag == false) {
            st.insert(a[i].second);
            count++;
        }
    }
 
    // Finally print the ans
    return count;
}
 
// Driver Code
int main()
{
 
    // Given starting and ending time
    int S[] = { 1, 8, 3, 2, 6 };
    int E[] = { 5, 10, 6, 5, 9 };
 
    // Given K and N
    int K = 2, N = sizeof(S)
                   / sizeof(S[0]);
 
    // Function call
    cout << maximumShops(S, E, N, K) << endl;
}

# Python3 program for the above approach
from bisect import bisect_left
 
# Function to find maximum shops
# that can be visited by K persons
def maximumShops(opening, closing, n,  k):
   
    # Store opening and closing
    # time of shops
    a = [[0, 0] for i in range(n)]
 
    for i in range(n):
        a[i][0] = opening[i]
        a[i][1] = closing[i]
 
    # Sort the pair of array
    a = sorted(a)
 
    # Stores the result
    count = 1
 
    # Stores current number of persons visiting
    # some shop with their ending time
    st = {}
    for i in range(n):
 
        # Check if current shop can be
        # assigned to a person who's
        # already visiting any other shop
        flag = False
 
        if (len(st) == 0):
            ar = list(st.keys())
 
            it = bisect_left(ar, a[i][0])
 
            if (it != 0):
                it -= 1
 
                # Checks if there is any person whose
                # closing time <= current shop opening
                # time
                if (ar[it] <= a[i][0]):
 
                    # Erase previous shop visited by the
                    # person satisfying the condition
                    del st[it]
 
                    # Insert new closing time of current
                    # shop for the person satisfying ṭhe
                    # condition
                    st[a[i][1]] = 1
 
                    # Increment the count by one
                    count += 1
                    flag = True
 
        # In case if no person have closing
        # time <= current shop opening time
        # but there are some persons left
        if (len(st) < k and flag == False):
            st[a[i][1]] = 1
            count += 1
             
    # Finally pr the ans
    return count
 
# Driver Code
if __name__ == '__main__':
 
    # Given starting and ending time
    S = [1, 8, 3, 2, 6]
    E = [5, 10, 6, 5, 9]
 
    # Given K and N
    K,N = 2, len(S)
 
    # Function call
    print (maximumShops(S, E, N, K))
 
    # This code is contributed by mohit kumar 29

4

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