Un algoritmo codicioso para recursos k-limitados

Question

Estoy estudiando algoritmos codiciosos y me pregunto la solución para un caso diferente.

Para el problema de selección de intervalo, queremos elegir el número máximo de actividades que no entren en conflicto entre sí, por lo que la selección del trabajo con la hora de finalización más temprana funciona.

Otro ejemplo; tenemos n puestos de trabajo y queremos comprar el menor número de recursos posible. Aquí, podemos ordenar todos los trabajos de izquierda a derecha, y cuando encontramos un nuevo punto de inicio, incrementamos un contador y cuando encontramos un punto final, disminuimos el contador. Entonces, el mayor valor que obtenemos de este contador será la cantidad de recursos que necesitamos comprar.

Pero, por ejemplo, ¿qué pasa si tenemos n tareas pero k recursos? ¿Qué pasa si no podemos permitirnos más de k recurso? ¿Cómo debería ser una solución codiciosa para eliminar la menor cantidad de tareas posible para satisfacer esto?

Además, si hay un nombre específico para el último problema que escribí, estaría encantado de escuchar eso.

Answer 1

Parece un caso general de la versión en la que tenemos un solo recurso.

Intuitivamente, tiene sentido ordenar los trabajos por tiempo de finalización y llevarlos uno a uno en ese orden. Ahora, en lugar del tiempo de finalización del último trabajo, hacemos un seguimiento de los tiempos de finalización de los últimos k trabajos aceptados en nuestros recursos. Para cada trabajo, verificamos si el tiempo de inicio de trabajos actual es mayor que el último trabajo en cualquiera de nuestros recursos. Si no se encuentra ese recurso, omitimos ese trabajo y avanzamos. Si se encuentra un recurso, asignamos ese trabajo a ese recurso y actualizamos la hora de finalización. Si hay más de un recurso capaz de asumir ese trabajo, tiene sentido asignarlo al recurso con la última hora de finalización.

Realmente no tengo una prueba de esta estrategia codiciosa, por lo que puede estar mal. Pero no puedo pensar en un caso en el que cambiar la elección nos permita encajar más empleos.