Alice, una estudiante, tiene mucha tarea en las próximas semanas. Cada tarea le lleva exactamente un día. Cada artículo también tiene una fecha límite y un impacto negativo en sus calificaciones (suponga un número real, puntos de bonificación solo por asumir la comparabilidad), si no cumple con la fecha límite.
Escriba una función que, dada una lista de (fecha límite, impacto en la calificación), calcule un cronograma para qué tarea hacer en ese día que minimiza la suma del impacto negativo en sus calificaciones.
Toda la tarea debe hacerse eventualmente, pero si no cumple con una fecha límite para un artículo, no importa qué tan tarde la entregue.
En una formulación alternativa:
ACME corp quiere suministrar agua a los clientes. Todos viven a lo largo de una calle cuesta arriba. ACME tiene varios pozos distribuidos a lo largo de la calle. Cada pozo tiene suficiente agua para un cliente. Los clientes ofertan diferentes cantidades de dinero para ser suministrados. El agua solo fluye cuesta abajo. Maximice los ingresos eligiendo a qué clientes abastecer.
Podemos ordenar los plazos usando la clasificación de cubetas (o simplemente asumir que ya los hemos ordenado por fecha límite).
Podemos resolver el problema fácilmente con un algoritmo codicioso, si primero clasificamos por impacto de pendiente descendente. Esa solución no será mejor que O (n log n).
Inspirado por la mediana de las medianas y los algoritmos de árbol de expansión lineal lineal aleatorio , sospecho que también podemos resolver mi problema de programación / flujo simple en tiempo lineal (¿aleatorio?).
Busco:
- un algoritmo de tiempo lineal (potencialmente aleatorio)
- o alternativamente un argumento de que el tiempo lineal no es posible
Como un trampolín:
- Ya he demostrado que solo saber qué elementos se pueden hacer antes de su fecha límite, es suficiente para reconstruir el cronograma completo en tiempo lineal. (Esa idea es la base de la segunda formulación donde solo estoy preguntando sobre el certificado).
- Un programa lineal simple (¡integral!) Puede modelar este problema.
- Usando la dualidad de este programa, uno puede verificar la solución propuesta de un candidato en tiempo lineal para la optimización, si también se le da la solución al programa dual. (Ambas soluciones se pueden representar en un número lineal de bits).
Idealmente, quiero resolver este problema en un modelo que solo usa la comparación entre los impactos de grado y no asume números allí.
Tengo dos enfoques para este problema: uno basado en treaps con fecha límite e impacto, el otro tipo QuickSelect basado en la elección de elementos de pivote aleatorio y la división de los elementos por impacto. Ambos tienen los peores casos que obligan a O (n log n) o peor desempeño, pero no he podido construir un caso especial simple que degrade el desempeño de ambos.