Colas de Prioridad: Ejercicios Prácticos y Soluciones
Ejercicios recomendados 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.
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.
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ón:StockPrice 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.
Tienes un carro con algunos asientos vacíos. El vehículo sólo circula hacia el este (es decir, no puede dar la vuelta y conducir hacia el oeste).
Dada la capacidad del vehículo como un número entero y un arreglo con la lista de viajes donde viajes[i] = [numPasajerosi, inicioi, destinoi]. Las ubicaciones se indican como el número de kilómetros hacia el este desde la ubicación inicial del carro. Retorna true si es posible recoger y dejar a todos los pasajeros de todos los viajes dados, o false en caso contrario.
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;
