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.
Ejemplo1:Entrada: tareas =["A","A","A","B","B","B"], n =2Salida:8Explicación:A->B-> inactivo ->A->B-> inactivo ->A->BHay al menos 2 unidades de tiempo entre dos tareas iguales.Ejemplo2:Entrada: tareas =["A","A","A","B","B","B"], n =0Salida:6Explicació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"]...Yasí sucesivamente.
def organizadorDeTareas(self,tareas:List[str],n: int)-> int: tiempo =0 ocurrenciasCaracteres =defaultdict(int)for caracter intareas: ocurrenciasCaracteres[caracter]+=1 heap =[]for caracter, cuenta in ocurrenciasCaracteres.items(): heap.append((-cuenta,caracter)) heapq.heapify(heap)whileheap: valoresTemporales =[]for _ inrange(n+1):ifheap: contadorActual, caracterActual = heapq.heappop(heap) valoresTemporales.append((contadorActual, caracterActual))for(cuenta, caracter)invaloresTemporales:if cuenta <-1: heapq.heappush(heap,(cuenta+1, caracter))ifheap: tiempo+=n+1else: 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.
ExplicaciónStockPrice stockPrice =newStockPrice();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.
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.
Ejemplo1:Entrada: eventos =[[1,2],[2,3],[3,4]]Salida:3Explicació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.Ejemplo2: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 =1for 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
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?
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
packagealgorithmics;importjava.util.Comparator;importjava.util.HashMap;importjava.util.Map;importjava.util.PriorityQueue;publicclassTaskOrganizer{publicstaticvoidmain(String[] args){char[] chars ={'A','A','A','B','B','B'};int n =2;System.out.println("Tasks Organizing: "+taskOrganizer(chars, n));}publicstaticinttaskOrganizer(char[] chars,int n){//Iterate the char array and load a Map<Character, Integer>Map<Character,Integer> charCounts =newHashMap<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 =newPriorityQueue<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;}}```packagealgorithmics;importjava.util.Comparator;importjava.util.HashMap;importjava.util.Map;importjava.util.PriorityQueue;publicclassTaskOrganizer{ publicstaticvoidmain(String\[] args){ char \[] chars ={'A','A','A','B','B','B'}; int n =2; System.*out*.println("Tasks Organizing: "+*taskOrganizer*(chars, n)); } publicstaticinttaskOrganizer(char \[] chars,int n){ //Iterate the char array and load a Map\<Character, Integer> Map\<Character,Integer> charCounts =newHashMap\<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 =newPriorityQueue\<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; }}
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 =0whiletrips: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:returnFalse # No se pudo aceptar un viaje
kilometer +=1returnTrue
