¿Qué algoritmo usar para este problema?

Question

Recientemente me enfrenté a una prueba de entrevista de Hackerrank, donde no podía resolver el siguiente problema correctamente. No quisiera nombrar el problema exacto con fines de privacidad, pero puedo decir que no estaba en ninguna parte en Google con este nombre.

problema

Queremos organizar un evento con la mayor cantidad de intérpretes como sea posible. Nos dan una lista de los posibles tiempos de llegada del intérprete y duraciones de rendimiento. Nuestra función debe devolver el número máximo de intérpretes que se pueden seleccionar sin conflictos.

Ejemplo

n= 5
LLEGADOS= [1, 3, 3, 5, 7] (los artistas llegan en estos tiempos)
Duraciones= [2, 2, 1, 2, 1] (el tiempo necesario para terminar sus actuaciones)
Solución= 4

Entonces, en el momento 1 podemos aceptar al intérprete y terminará en el tiempo 3. En el momento 3, tenemos dos opciones conflictivas, y no importa cuál elegimos. El tiempo 5 y 7 tampoco están en conflicto.

mi solución

1. hizo tuples de las llegadas y duraciones por cremallera. Ordenó los tuples primero a la llegada, luego de duración.
2. EXTERIOR para el ciclo para que comience a terminar. Inicialice el nuevo conjunto en cada iter.
3. interno para el ciclo por j de la que termine. Compruebe si J se puede agregar al conjunto sin conflicto. Si el set es más largo que el máximo, guardo.

fuente de Python

Preguntas

1. ¿Hay mejores formas, algoritmos estándar para resolver este problema?
2. Sé que hay algunos casos de borde, para los cuales mi algoritmo no funciona. HackerRank evaluó mi Algo, y solo pasó 7/13 casos de prueba. ¿Qué podrían ser algunos casos de ventaja? ¿Me estoy perdiendo?
3. ¿Es este un problema de búsqueda o un problema de optimización?

Answer 1

Este es un simple maximización de programación de intervalo problema, que se puede resolver en < em> o (n log (n)) tiempo a través de un simple algoritmo codicioso. El truco es ordenar las actuaciones de acuerdo con Tiempo final y no Tiempo de inicio .

Aquí está la descripción de la solución que se encuentra en la página de Wikipedia que vinculé:

---

Varios algoritmos, que pueden parecer prometedores a primera vista, en realidad no encuentran la solución óptima:

• Selección de los intervalos que comienzan más temprano no es una solución óptima, porque si el intervalo más temprano es muy largo, aceptarlo nos haría rechazar muchas otras solicitudes más cortas.

• Selección de los intervalos más cortos o seleccionando intervalos con menos conflictos tampoco es óptimo.

Solución polinomial codiciosa

El siguiente algoritmo codicioso encuentra la solución óptima:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Cada vez que seleccionamos un intervalo en el Paso 1, es posible que tengamos que eliminar muchos intervalos en el Paso 2. Sin embargo, todos estos intervalos deben cruzar necesariamente el tiempo de acabado de X y, por lo tanto, todos se cruzan entre sí. Por lo tanto, a lo sumo 1 de estos intervalos puede estar en la solución óptima. Por lo tanto, para cada intervalo en la solución óptima, hay un intervalo en la solución codiciosa. Esto demuestra que el algoritmo codicioso consigue una solución óptima.

Una explicación más formal está dada por una argumento de carga .

El algoritmo codicioso se puede ejecutar en el tiempo o (n log n) , donde n es el número de tareas, utilizando un paso de preprocesamiento en el que se ordenan las tareas por sus tiempos de acabado.

---

Answer 2

Mira a Programación de intervalo máximo .

Asignar un intervalo $ (s_i, t_i) $ a cada intérprete, para $ i= 1, \ puntos, N $ , lo que significa que el rendimiento comienza en el momento $ s_i $ y tiene una duración de $ t_i - s_i $ .

Asumir por ahora que todos los intervalos están ordenados por su tiempo final. Solo por simplicidad asume también que todos los tiempos son distintos (este supuesto es innecesario). Su problema se puede resolver en $ o (n) $ tiempo.

Considere $ (s_1, t_1) $ y deje que $ i $ sea el conjunto de intervalos que interseccione (excluyendo $ (s_1, t_1) $ mismo).

es fácil de ver que todos los intervalos en $ i $ deben comenzar antes de $ t_1 $ ( Como de lo contrario, no se intersecarían $ (s_1, t_1) $ ) y terminan después de $ t_1 $ ( De lo contrario, $ t_1 $ no sería el tiempo mínimo de finalización). Esto significa que todos los intervalos en $ i \ Cup \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ span> se intersectan entre sí y, por lo tanto, cualquier solución puede contener como la mayoría de ellos.

Permitir $ s $ ser una solución (es decir, un subconjunto de intervalos no intersectores por pares). Siempre es posible convertir $ s $ en una nueva solución $ s '$ que contiene $ (S_1, T_1) $ y tal que $ | s '| \ ge | s | $ .

Si $ s \ cap I=vacioset $ luego estamos hechos trivialmente ya que podemos elegir $ s '= S \ Cup \ {(S_1, T_1) \} $ (notifique que esto también incluye el caso en el que $ (s_1, t_1) \ in s $ ).

Si $ s \ cap I \ NEQ \ STOPSET $ , deja $ (s_i, t_i) $ Sea el intervalo único en $ s \ tap i $ . Cualquier intervalo $ (s_j, t_j) \ in s \ setminus \ {(s_i, t_i) \ \ _} $ debe satisfacer cualquiera de los $ s_j> t_i> t_1 $ o $ s_i> t_j> t_1 $ . Este último caso es realmente imposible, ya que contradeciría el hecho de que $ (s_i, t_i) \ in s $ . En otras palabras, si reemplazamos $ (s_i, t_i) $ con $ (s_1, t_1) $ Todavía obtenemos una solución factible. Por lo tanto, elegimos $ s '= s \ cucas \ {(s_1, t_1) \ \ \ setminus \ {(s_i, t_i) \}}}} $ .

La línea inferior es que siempre hay una solución óptima que contiene $ (s_1, t_1) $ . Por lo tanto, siempre puede agregar $ (s_1, t_1) $ a su solución, elimine todos los intervalos en $ s \ cuco \ { (S_1, T_1) \} $ y busque la solución óptima entre los intervalos restantes. Esto equivale a ejecutar el algoritmo codicioso que considera los intervalos en orden y agrega cualquier intervalo que se ajuste.

De su instancia Parece que los tiempos de inicio ya están ordenados. En este caso, puede hacer el truco de "revertir el tiempo", es decir, intercambiar los tiempos de inicio y finalización, por ejemplo, cambiando $ (s_i, t_i) $ en $ (- t_i, -s_i) $ , que le permite obtener un $ o (n) $ Algoritmo -timo de tiempo saltando el paso de clasificación inicial que ya requeriría $ \ omega (n \ log n) $ tiempo.