Colas de Prioridad y Gestión de Eventos

Clase 40 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Ejercicios resueltos de Colas de Prioridad

Organizador de Tareas

Tienes un arreglo de caracteres tasks que representa las tareas que debe realizar una CPU, donde cada letra representa una tarea diferente. Las tareas pueden realizarse en cualquier orden. Cada tarea se realiza en una unidad de tiempo. Por cada unidad de tiempo la CPU puede completar una tarea o simplemente estar inactiva.

Sin embargo, existe un período de enfriamiento entre dos tareas iguales (la misma letra en la matriz) representado por la variable n, es decir que debe haber al menos n unidades de tiempo entre dos tareas iguales.

Devuelve el menor número de unidades de tiempo que la CPU tardará en terminar todas las tareas dadas.

Ejemplo 1:
    Entrada: tareas = ["A", "A", "A", "B", "B", "B"], n = 2
    Salida: 8

Explicación:
A -> B -> inactivo -> A -> B -> inactivo -> A -> B
Hay al menos 2 unidades de tiempo entre dos tareas iguales.


Ejemplo 2:
    Entrada: tareas = ["A", "A", "A", "B", "B", "B"], n = 0
    Salida: 6
Explicación: En este caso cualquier permutación de tamaño 6 funcionaría ya que n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
Y así sucesivamente.

def organizadorDeTareas(self, tareas: List[str], n: int) -> int:
   tiempo = 0
   ocurrenciasCaracteres = defaultdict(int)
   for caracter in tareas:
       ocurrenciasCaracteres[caracter]+=1
   heap = []
   for caracter, cuenta in ocurrenciasCaracteres.items():
       heap.append((-cuenta,caracter))
   heapq.heapify(heap)
   while heap:
       valoresTemporales = []
       for _ in range(n+1):
           if heap:
               contadorActual, caracterActual = heapq.heappop(heap)
               valoresTemporales.append((contadorActual, caracterActual))
      
       for (cuenta, caracter) in valoresTemporales:
           if cuenta < -1:
               heapq.heappush(heap,(cuenta+1, caracter))
              
       if heap:
           tiempo+=n+1
       else:
           tiempo+=len(valoresTemporales)
   return tiempo

Fluctuación del Precio de Acciones

Se le da un flujo de registros sobre una acción concreta. Cada registro contiene el tiempo y el precio correspondiente de la acción en esa marca. Por desgracia, debido a la naturaleza volátil del mercado de valores, los registros no vienen en orden y algunos registros pueden ser incorrectos. Otro registro con el mismo registro de tiempo puede aparecer más tarde en el flujo corrigiendo el precio del anterior registro erróneo.

Diseñe un algoritmo que: Actualice el precio de la acción en un momento en el tiempo determinado, corrigiendo el precio de cualquier registro anterior en ese instante. Encuentre el último precio de la acción basado en los registros actuales. El último precio es el precio de la última marca de tiempo registrada. Busque el precio máximo de la acción basado en los registros actuales. Encuentre el precio mínimo de la acción basado en los registros actuales.

Implementa la clase StockPrice: StockPrice(): inicializa el objeto sin registros de precios. void update(int timestamp, int price): actualiza el precio de la acción en el timestamp dado. int current(): devuelve el último precio de la acción. int maximum(): devuelve el precio máximo de la acción. int minimum(): devuelve el precio mínimo de la acción.

Ejemplo:
Entrada.
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Salida: [null, null, null, 5, 10, null, 5, null, 2]

Explicación
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Las marcas de tiempo son [1] con los precios correspondientes [10].
stockPrice.update(2, 5); // Las marcas de tiempo son [1,2] con los precios correspondientes [10,5].
stockPrice.current(); // devuelve 5, la última marca de tiempo es 2 con el precio siendo 5.
stockPrice.maximum(); // devuelve 10, el precio máximo es 10 en el timestamp 1.
stockPrice.update(1, 3); // El timestamp 1 anterior tenía el precio incorrecto, por lo que se actualiza a 3.
                          // Las marcas de tiempo son [1,2] con los precios correspondientes [3,5].
stockPrice.maximum(); // devuelve 5, el precio máximo es 5 después de la corrección.
stockPrice.update(4, 2); // Las marcas de tiempo son [1,2,4] con los precios correspondientes [3,5,2].
stockPrice.minimum(); // devuelve 2, el precio mínimo es 2 en el timestamp 4.

class StockPrice:
   def __init__(self):
       self.hash_map = {}
       self.ultimo = 0
       self.minHeap = []
       self.maxHeap = []
 
   def update(self, t: int, p: int) -> None:
       self.ultimo = max(t, self.ultimo)
       self.hash_map[t] = p
       heappush(self.minHeap, (p, t))
       heappush(self.maxHeap, (-p, t))

   def current(self) -> int:
       return self.hash_map[self.ultimo]
 
   def maximum(self) -> int:
       while self.hash_map[self.maxHeap[0][1]] != -self.maxHeap[0][0]:
           heappop(self.maxHeap)
       return -self.maxHeap[0][0]
 
   def minimum(self) -> int:
       while self.hash_map[self.minHeap[0][1]] != self.minHeap[0][0]:
           heappop(self.minHeap)
       return self.minHeap[0][0]

Número máximo de eventos a los que se puede asistir

Dado un array de eventos donde events[i] = [comienzoDiai, finalDiai]. Cada evento i comienza en comienzoDiai y termina en finalDiai. Puedes asistir a un evento i en cualquier día d donde startTimei <= d <= endTimei. Sólo se puede asistir a un evento en cualquier momento d. Devuelve el número máximo de eventos a los que puedes asistir.

Ejemplo 1:
    Entrada: eventos = [[1,2],[2,3],[3,4]]
    Salida: 3

Explicación: Puedes asistir a los tres eventos.
Una forma de asistir a todos ellos es la que se muestra.
Asistir al primer evento en el día 1.
Asistir al segundo evento el día 2.
Asistir al tercer evento el día 3.


Ejemplo 2:
    Entrada: eventos= [[1,2],[2,3],[3,4],[1,2]]
    Salida: 4

def maxEventos(self, eventos: List[List[int]]) -> int:
   eventos.sort(key=lambda x: x[0])
   cuentaAtendidos = 0
   listaEventosAtendidos = []
   dia = 1
   for comienzo, final in eventos + [[sys.maxsize, 0]]:
       while dia < comienzo and listaEventosAtendidos:
           evento = heappop(listaEventosAtendidos)
           if dia <= evento:
               cuentaAtendidos += 1
               dia += 1
       dia = max(dia, comienzo)
       heappush(listaEventosAtendidos, final)
   return cuentaAtendidos

Juan Pablo Reina Gutierrez

student•

En el ejercicio de 'Número máximo de eventos a los que se puede asistir' el número máximo de eventos no sería siempre el mismo que la longitud de la lista de entrada?

José Ramón García

student•

El objetivo es determinar el número máximo de eventos que se pueden atender, suponiendo que cada evento se puede asistir solo un día y no se pueden asistir dos eventos el mismo día.

si tuvieras [1,3] , [2,3], [1,2] y [1,2] solo podrias asistir a 3 eventos

Nicolas Lopez

student•

package algorithmics;


import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TaskOrganizer {

    public static void main(String[] args) {
        char [] chars = {'A', 'A', 'A', 'B', 'B', 'B'};
        int n = 2;
        System.out.println("Tasks Organizing: " + taskOrganizer(chars, n));
    }

    public static int taskOrganizer(char [] chars, int n) {

        //Iterate the char array and load a Map<Character, Integer>
        Map<Character, Integer> charCounts = new HashMap<Character, Integer>();
        for (int i = 0; i < chars.length; i++) {
            charCounts.put(chars[i], charCounts.getOrDefault(chars[i], 0) + 1);
        }

        //The Map should have > 1 and <= 2.
        if (charCounts.size() != 2) {return -1;}

        //Create a PriorityQueue<Map<Character, Integer>> comparing by charCounts.value.
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<Map.Entry<Character, Integer>>(Comparator.comparing(Map.Entry::getValue));
        pq.addAll(charCounts.entrySet());

        /*for (int i = 0; i < n; i++) {
            char c = pq.peek().getKey();
            System.out.println("Key -> " + pq.peek().getKey() + "Value -> " + charCounts.get(pq.poll().getKey()));
        }*/

        //Create an int taskCounter.
        int taskCount = 0;
        int nCounter = 0;

        while (!pq.isEmpty()) {
            char c1 = pq.poll().getKey();
            char c2 = pq.poll().getKey();

            if (c1 != c2) {
                taskCount += 2;
                if(nCounter < n){
                    nCounter++;
                    taskCount++;
                }
            }

            charCounts.put(c1, charCounts.getOrDefault(c1, 0) - 1);
            charCounts.put(c2, charCounts.getOrDefault(c2, 0) - 1);

            if(charCounts.get(c1) > 0 || charCounts.get(c2) > 0){
                pq.addAll(charCounts.entrySet());
            }
        }
        return taskCount;
    }
}
```package algorithmics;


import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TaskOrganizer {

&#x20;   public static void main(String\[] args) {
&#x20;       char \[] chars = {'A', 'A', 'A', 'B', 'B', 'B'};
&#x20;       int n = 2;
&#x20;       System.*out*.println("Tasks Organizing: " + *taskOrganizer*(chars, n));
&#x20;   }

&#x20;   public static int taskOrganizer(char \[] chars, int n) {

&#x20;       //Iterate the char array and load a Map\<Character, Integer>
&#x20;       Map\<Character, Integer> charCounts = new HashMap\<Character, Integer>();
&#x20;       for (int i = 0; i < chars.length; i++) {
&#x20;           charCounts.put(chars\[i], charCounts.getOrDefault(chars\[i], 0) + 1);
&#x20;       }

&#x20;       //The Map should have > 1 and <= 2.
&#x20;       if (charCounts.size() != 2) {return -1;}

&#x20;       //Create a PriorityQueue\<Map\<Character, Integer>> comparing by charCounts.value.
&#x20;       PriorityQueue\<Map.Entry\<Character, Integer>> pq = new PriorityQueue\<Map.Entry\<Character, Integer>>(Comparator.*comparing*(Map.Entry::getValue));
&#x20;       pq.addAll(charCounts.entrySet());

&#x20;       /\*for (int i = 0; i < n; i++) {
&#x20;           char c = pq.peek().getKey();
&#x20;           System.out.println("Key -> " + pq.peek().getKey() + "Value -> " + charCounts.get(pq.poll().getKey()));
&#x20;       }\*/
&#x20;       //Create an int taskCounter.
&#x20;       int taskCount = 0;
&#x20;       int nCounter = 0;

&#x20;       while (!pq.isEmpty()) {
&#x20;           char c1 = pq.poll().getKey();
&#x20;           char c2 = pq.poll().getKey();

&#x20;           if (c1 != c2) {
&#x20;               taskCount += 2;
&#x20;               if(nCounter < n){
&#x20;                   nCounter++;
&#x20;                   taskCount++;
&#x20;               }
&#x20;           }

&#x20;           charCounts.put(c1, charCounts.getOrDefault(c1, 0) - 1);
&#x20;           charCounts.put(c2, charCounts.getOrDefault(c2, 0) - 1);

&#x20;           if(charCounts.get(c1) > 0 || charCounts.get(c2) > 0){
&#x20;               pq.addAll(charCounts.entrySet());
&#x20;           }
&#x20;       }
&#x20;       return taskCount;
&#x20;   }
}

Luis Antonio Ibarra Salgado

student•

Dejo como resolvi el ejercicio de Car Pooling:

def car_pooling(trips: list[list[int]], capacity: int) -> bool:
    trips.sort(key=lambda x: x[1]) # Ordenamos por inicios de viajes
    ongoing_trips = [] # heap para registrar los viajes que aceptas [[kilometroFinal, noPasajeros]]
    kilometer = 0

    while trips:

        while ongoing_trips and kilometer == ongoing_trips[0][0]:
            capacity += ongoing_trips[0][1]
            heapq.heappop(ongoing_trips)

        while trips and kilometer == trips[0][1]:
            if capacity >= trips[0][0]:
                heapq.heappush(ongoing_trips, [trips[0][2], trips[0][0]])
                capacity -= trips[0][0]
                trips.pop(0) # Eliminamos de la lista el viaje tomado
            else:
                return False # No se pudo aceptar un viaje
            
        kilometer += 1
    return True

Ejemplo 1:
    Entrada: tareas = ["A", "A", "A", "B", "B", "B"], n = 2
    Salida: 8

Explicación:
A -> B -> inactivo -> A -> B -> inactivo -> A -> B
Hay al menos 2 unidades de tiempo entre dos tareas iguales.


Ejemplo 2:
    Entrada: tareas = ["A", "A", "A", "B", "B", "B"], n = 0
    Salida: 6
Explicación: En este caso cualquier permutación de tamaño 6 funcionaría ya que n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
Y así sucesivamente.

def organizadorDeTareas(self, tareas: List[str], n: int) -> int:
   tiempo = 0
   ocurrenciasCaracteres = defaultdict(int)
   for caracter in tareas:
       ocurrenciasCaracteres[caracter]+=1
   heap = []
   for caracter, cuenta in ocurrenciasCaracteres.items():
       heap.append((-cuenta,caracter))
   heapq.heapify(heap)
   while heap:
       valoresTemporales = []
       for _ in range(n+1):
           if heap:
               contadorActual, caracterActual = heapq.heappop(heap)
               valoresTemporales.append((contadorActual, caracterActual))
      
       for (cuenta, caracter) in valoresTemporales:
           if cuenta < -1:
               heapq.heappush(heap,(cuenta+1, caracter))
              
       if heap:
           tiempo+=n+1
       else:
           tiempo+=len(valoresTemporales)
   return tiempo

Ejemplo:
Entrada.
["StockPrice", "update", "update", "current", "maximum", "update", "maximum", "update", "minimum"]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Salida: [null, null, null, 5, 10, null, 5, null, 2]

Explicación
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Las marcas de tiempo son [1] con los precios correspondientes [10].
stockPrice.update(2, 5); // Las marcas de tiempo son [1,2] con los precios correspondientes [10,5].
stockPrice.current(); // devuelve 5, la última marca de tiempo es 2 con el precio siendo 5.
stockPrice.maximum(); // devuelve 10, el precio máximo es 10 en el timestamp 1.
stockPrice.update(1, 3); // El timestamp 1 anterior tenía el precio incorrecto, por lo que se actualiza a 3.
                          // Las marcas de tiempo son [1,2] con los precios correspondientes [3,5].
stockPrice.maximum(); // devuelve 5, el precio máximo es 5 después de la corrección.
stockPrice.update(4, 2); // Las marcas de tiempo son [1,2,4] con los precios correspondientes [3,5,2].
stockPrice.minimum(); // devuelve 2, el precio mínimo es 2 en el timestamp 4.

class StockPrice:
   def __init__(self):
       self.hash_map = {}
       self.ultimo = 0
       self.minHeap = []
       self.maxHeap = []
 
   def update(self, t: int, p: int) -> None:
       self.ultimo = max(t, self.ultimo)
       self.hash_map[t] = p
       heappush(self.minHeap, (p, t))
       heappush(self.maxHeap, (-p, t))

   def current(self) -> int:
       return self.hash_map[self.ultimo]
 
   def maximum(self) -> int:
       while self.hash_map[self.maxHeap[0][1]] != -self.maxHeap[0][0]:
           heappop(self.maxHeap)
       return -self.maxHeap[0][0]
 
   def minimum(self) -> int:
       while self.hash_map[self.minHeap[0][1]] != self.minHeap[0][0]:
           heappop(self.minHeap)
       return self.minHeap[0][0]

Ejemplo 1:
    Entrada: eventos = [[1,2],[2,3],[3,4]]
    Salida: 3

Explicación: Puedes asistir a los tres eventos.
Una forma de asistir a todos ellos es la que se muestra.
Asistir al primer evento en el día 1.
Asistir al segundo evento el día 2.
Asistir al tercer evento el día 3.


Ejemplo 2:
    Entrada: eventos= [[1,2],[2,3],[3,4],[1,2]]
    Salida: 4

def maxEventos(self, eventos: List[List[int]]) -> int:
   eventos.sort(key=lambda x: x[0])
   cuentaAtendidos = 0
   listaEventosAtendidos = []
   dia = 1
   for comienzo, final in eventos + [[sys.maxsize, 0]]:
       while dia < comienzo and listaEventosAtendidos:
           evento = heappop(listaEventosAtendidos)
           if dia <= evento:
               cuentaAtendidos += 1
               dia += 1
       dia = max(dia, comienzo)
       heappush(listaEventosAtendidos, final)
   return cuentaAtendidos

package algorithmics;


import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TaskOrganizer {

    public static void main(String[] args) {
        char [] chars = {'A', 'A', 'A', 'B', 'B', 'B'};
        int n = 2;
        System.out.println("Tasks Organizing: " + taskOrganizer(chars, n));
    }

    public static int taskOrganizer(char [] chars, int n) {

        //Iterate the char array and load a Map<Character, Integer>
        Map<Character, Integer> charCounts = new HashMap<Character, Integer>();
        for (int i = 0; i < chars.length; i++) {
            charCounts.put(chars[i], charCounts.getOrDefault(chars[i], 0) + 1);
        }

        //The Map should have > 1 and <= 2.
        if (charCounts.size() != 2) {return -1;}

        //Create a PriorityQueue<Map<Character, Integer>> comparing by charCounts.value.
        PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<Map.Entry<Character, Integer>>(Comparator.comparing(Map.Entry::getValue));
        pq.addAll(charCounts.entrySet());

        /*for (int i = 0; i < n; i++) {
            char c = pq.peek().getKey();
            System.out.println("Key -> " + pq.peek().getKey() + "Value -> " + charCounts.get(pq.poll().getKey()));
        }*/

        //Create an int taskCounter.
        int taskCount = 0;
        int nCounter = 0;

        while (!pq.isEmpty()) {
            char c1 = pq.poll().getKey();
            char c2 = pq.poll().getKey();

            if (c1 != c2) {
                taskCount += 2;
                if(nCounter < n){
                    nCounter++;
                    taskCount++;
                }
            }

            charCounts.put(c1, charCounts.getOrDefault(c1, 0) - 1);
            charCounts.put(c2, charCounts.getOrDefault(c2, 0) - 1);

            if(charCounts.get(c1) > 0 || charCounts.get(c2) > 0){
                pq.addAll(charCounts.entrySet());
            }
        }
        return taskCount;
    }
}
```package algorithmics;


import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TaskOrganizer {

&#x20;   public static void main(String\[] args) {
&#x20;       char \[] chars = {'A', 'A', 'A', 'B', 'B', 'B'};
&#x20;       int n = 2;
&#x20;       System.*out*.println("Tasks Organizing: " + *taskOrganizer*(chars, n));
&#x20;   }

&#x20;   public static int taskOrganizer(char \[] chars, int n) {

&#x20;       //Iterate the char array and load a Map\<Character, Integer>
&#x20;       Map\<Character, Integer> charCounts = new HashMap\<Character, Integer>();
&#x20;       for (int i = 0; i < chars.length; i++) {
&#x20;           charCounts.put(chars\[i], charCounts.getOrDefault(chars\[i], 0) + 1);
&#x20;       }

&#x20;       //The Map should have > 1 and <= 2.
&#x20;       if (charCounts.size() != 2) {return -1;}

&#x20;       //Create a PriorityQueue\<Map\<Character, Integer>> comparing by charCounts.value.
&#x20;       PriorityQueue\<Map.Entry\<Character, Integer>> pq = new PriorityQueue\<Map.Entry\<Character, Integer>>(Comparator.*comparing*(Map.Entry::getValue));
&#x20;       pq.addAll(charCounts.entrySet());

&#x20;       /\*for (int i = 0; i < n; i++) {
&#x20;           char c = pq.peek().getKey();
&#x20;           System.out.println("Key -> " + pq.peek().getKey() + "Value -> " + charCounts.get(pq.poll().getKey()));
&#x20;       }\*/
&#x20;       //Create an int taskCounter.
&#x20;       int taskCount = 0;
&#x20;       int nCounter = 0;

&#x20;       while (!pq.isEmpty()) {
&#x20;           char c1 = pq.poll().getKey();
&#x20;           char c2 = pq.poll().getKey();

&#x20;           if (c1 != c2) {
&#x20;               taskCount += 2;
&#x20;               if(nCounter < n){
&#x20;                   nCounter++;
&#x20;                   taskCount++;
&#x20;               }
&#x20;           }

&#x20;           charCounts.put(c1, charCounts.getOrDefault(c1, 0) - 1);
&#x20;           charCounts.put(c2, charCounts.getOrDefault(c2, 0) - 1);

&#x20;           if(charCounts.get(c1) > 0 || charCounts.get(c2) > 0){
&#x20;               pq.addAll(charCounts.entrySet());
&#x20;           }
&#x20;       }
&#x20;       return taskCount;
&#x20;   }
}

def car_pooling(trips: list[list[int]], capacity: int) -> bool:
    trips.sort(key=lambda x: x[1]) # Ordenamos por inicios de viajes
    ongoing_trips = [] # heap para registrar los viajes que aceptas [[kilometroFinal, noPasajeros]]
    kilometer = 0

    while trips:

        while ongoing_trips and kilometer == ongoing_trips[0][0]:
            capacity += ongoing_trips[0][1]
            heapq.heappop(ongoing_trips)

        while trips and kilometer == trips[0][1]:
            if capacity >= trips[0][0]:
                heapq.heappush(ongoing_trips, [trips[0][2], trips[0][0]])
                capacity -= trips[0][0]
                trips.pop(0) # Eliminamos de la lista el viaje tomado
            else:
                return False # No se pudo aceptar un viaje
            
        kilometer += 1
    return True

Colas de Prioridad y Gestión de Eventos

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles