Activity Selection Problem
La actividad i va desde el momento start[i] hasta el momento finish[i]. Una persona realiza una actividad a la vez, y la siguiente actividad debe comenzar estrictamente después de que termine la anterior: una actividad que comienza justo cuando termina otra no puede realizarse después de ella.
Devuelve el número máximo de actividades que una persona puede realizar.
Función
- startinteger-array
- la hora de inicio de cada actividad
- finishinteger-array
- la hora de finalización de cada actividad; finish[i] corresponde a start[i]
- Devuelveinteger
- la mayor cantidad de actividades que una persona puede hacer, una tras otra
Restricciones
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- Una actividad puede comenzar y terminar al mismo tiempo. Los arreglos no están ordenados.
Ejemplos
- Entrada
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- Salida
- 4
- Explicación
- Hacer del 10 al 13, del 14 al 19, del 21 al 22 y del 25 al 30 da 4. Cinco es imposible: del 10 al 13 entra en conflicto con del 12 al 16, y del 21 al 22 con del 20 al 24.
- Entrada
- start = [1, 5, 9]finish = [5, 9, 12]
- Salida
- 2
- Explicación
- La actividad de 5 a 9 empieza justo cuando termina la primera, así que no puede ir después de ella. Hacer de 1 a 5 y después de 9 a 12 funciona, así que la respuesta es
2.
- Entrada
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- Salida
- 3
- Explicación
- La actividad de 0 a 100 se superpone a todas las demás. Si la dejamos fuera, de 2 a 4, de 5 a 7 y de 8 a 10 encajan una después de otra:
3.
Para ir más allá
Ahora dos personas trabajan en paralelo, cada una realizando una actividad a la vez. ¿Cuántas actividades pueden hacer juntas y qué persona debería encargarse de cada una?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Supongamos que ya sabes qué actividad haces primero. ¿Cuál querrías que fuera para que después te quede la mayor cantidad de tiempo posible?
La actividad que termina antes siempre es una primera opción segura: un plan que empieza con cualquier otra actividad puede sustituirla por la que termina antes y mantener la misma cantidad. Después, la misma pregunta se repite para las actividades que empiezan después de que esta termina.
Ordena las actividades por hora de finalización, moviendo cada hora de inicio junto con su hora de finalización. Recorre la lista ordenada conservando la hora de finalización de la última actividad que elegiste y elige cada actividad cuya hora de inicio sea estrictamente posterior a esa hora.
Solución
Probar cada subconjunto de actividades lleva un tiempo exponencial. En cambio, una regla voraz resuelve la cuestión: entre las actividades que aún caben, elige siempre la que termina primero. Ordenarlas por hora de finalización convierte esa regla en un solo recorrido.
Elige el final más temprano, una y otra vez
Correcto, pero no termina con las pruebas más grandes
Intuición
La actividad que termina antes que todas es, como mínimo, una primera elección tan buena como cualquier otra. Te deja libre no más tarde, así que cualquier actividad que pudiera ir después de otra primera elección también puede ir después de ella, y sustituirla mantiene la cantidad. Después de esa elección, el problema se repite con las actividades que empiezan después de que termina.
En el primer ejemplo eliges de 10 a 13, después de 14 a 19, después de 21 a 22 y después de 25 a 30: cuatro.
Cada elección recorre las n actividades, así que el costo es n veces la respuesta. Cuando las 5000 actividades caben una después de otra, eso son 25 millones de comprobaciones.
Algoritmo
- Establece
count = 0ylastFinish = -1, debajo de cada inicio. - Recorre todas las actividades para encontrar la que cumple
start[i] > lastFinishy termina primero. - Si no hay ninguna, devuelve
count. - De lo contrario, suma 1 a
count, establecelastFinishen el final de esa actividad y vuelve a recorrerlas.
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]Ordena por hora de finalización y selecciona de forma voraz
Intuición
Ordena por hora de finalización una vez y encontrarás las actividades en el orden en que las buscaron los recorridos de arriba. Recorre la lista ordenada guardando lastFinish, la hora de finalización de la última actividad que elegiste. Una actividad con start[i] > lastFinish es la que termina antes y todavía encaja, así que elígela. Cualquier otra se solapa con tu última elección, por lo que omitirla no cuesta nada.
Ordenado, el primer ejemplo queda así: de 10 a 13, de 12 a 16, de 14 a 19, de 21 a 22, de 20 a 24, de 25 a 30. Eliges la primera, la tercera, la cuarta y la sexta: 12 no es posterior a 13, y 20 no es posterior a 22.
No hace falta una regla para los empates en la hora de finalización. Una vez que eliges una actividad que termina en t, todas las demás que terminan en t empiezan en t o antes, así que se omiten.
Algoritmo
- Ordena las actividades por
finish, moviendo cada inicio junto con su finalización. - Establece
count = 0ylastFinish = -1. - Para cada actividad en ese orden, si
start[i] > lastFinish, suma 1 acounty establecelastFinish = finish[i]. - Devuelve
count.
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
Errores comunes y casos límite
- Ordenar por hora de inicio. En el tercer ejemplo, la actividad de 0 a 100 empieza primero y bloquea las otras tres.
- Elegir primero la actividad más corta. Con las actividades de 1 a 5, de 5 a 6 y de 6 a 10, la más corta es de 5 a 6, que entra en conflicto con las otras dos; las actividades de 1 a 5 y de 6 a 10 dan 2.
- Comparar con
≥en lugar de>. En el segundo ejemplo, eso devuelve 3 en lugar de 2. - Ordenar
finishpor separado. Cada hora de inicio debe mantenerse junto con su propia hora de finalización; de lo contrario, las horas de inicio se emparejan con las actividades incorrectas. - Empezar
lastFinishen 0. Así se omite una actividad única de 0 a 1, porque0 > 0es falso.
Preguntas frecuentes3
¿Cuál es la complejidad temporal del problema de selección de actividades?
Ordenar por hora de finalización cuesta O(n log n), y el recorrido voraz posterior cuesta O(n), así que domina la ordenación. Si las actividades ya están ordenadas por hora de finalización, el recorrido por sí solo lo resuelve en O(n) de tiempo y O(1) de espacio adicional.
¿Qué es el problema de las N reuniones en una sala?
Es el mismo problema planteado con reuniones: una sala, N reuniones, y una reunión solo puede comenzar después de que haya terminado la anterior. Ordena las reuniones por hora de finalización y elige cada una que empiece después de que termine la última elegida. Para enumerar las reuniones, registra cada índice que elijas; si coinciden las horas de finalización, desempata usando el índice menor.
¿Es el problema de selección de actividades un problema de programación dinámica?
Puede serlo, pero no es necesario. Una tabla de actividades ordenadas por hora de finalización, que contenga el mayor número de actividades que terminan con cada una, da la respuesta en O(n²). La elección voraz siempre es segura, así que basta con una sola pasada. La tabla se convierte en la herramienta adecuada cuando las actividades tienen valores y quieres maximizar su total.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def maxActivities(start, finish):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
Salida Esperada
4