Colas de Prioridad y Gestión de Eventos

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