algorithm - keywords - FInd citas superpuestas en el tiempo O(n)?

meta tags seo 2018

Question

Hace poco me preguntaron esta pregunta en una entrevista. Aunque pude encontrar la solución O ( n ²), el entrevistador estaba obsesionado con una solución O ( n ). También verifiqué algunas otras soluciones de O ( n log n ) que entendí, pero la solución O ( n ) aún no es mi taza de té, que asume las citas ordenadas por el tiempo de inicio.

¿Alguien puede explicar esto?

Declaración del problema: le dan n citas. Cada cita contiene una hora de inicio y una hora de finalización. Debe volver a escribir todas las citas conflictivas de manera eficiente.

Persona: 1,2, 3, 4, 5
Inicio de la aplicación: 2, 4, 29, 10, 22
Final de la aplicación: 5, 7, 34, 11, 36

Respuesta: 2x1 5x3

Algoritmo O ( n log n ): punto de inicio y final separados como este:

2s, 4s, 29s, 10s, 22s, 5e, 7e, 34e, 11e, 36e

luego ordena todos estos puntos (para simplificar, supongamos que cada punto es único):

2s, 4s, 5e, 7e, 10s, 11e, 22s, 29s, 34e, 36e

si tenemos inicios consecutivos sin fines, entonces se superpone: 2s, 4s son adyacentes, por lo que se superponen

Mantendremos un conteo de "s" y cada vez que nos encontremos tendrá +1, y cuando se encuentra e disminuimos la cuenta en 1.

Answer 1

Encontré una estructura de datos llamada árbol Interval, con la ayuda de la cual podemos encontrar intervalos en menos de O (n log (n)) tiempo, dependiendo de los datos provistos

Answer 2

Esto es lo mejor que se me ocurre, en un pseudocódigo horrible. Intenté reducir el problema tanto como sea posible. Esto es solo menos que en ^ 2 (creo).

Tenga en cuenta que la salida al final no mostrará todas las citas con las que una cita determinada entrará en conflicto en la línea de salida específica de esa cita ... pero en algún momento se mostrará cada conflicto.

También tenga en cuenta que cambié el nombre de las citas numéricamente en orden de tiempo de inicio.

output would be something like the following:

Appointment 1 conflicts with 2
Appointment 2 conflicts with
Appointment 3 conflicts with
Appointment 4 conflicts with 5
Appointment 5 conflicts with

appt{1},appt{2},appt{3} ,appt{4} ,appt{5}
  2      4       10       22      29
  5      7       11       36      34

pseudocódigo

list=(1,2,3,4,5)
for (i=1,i<=5,i++)
    list.shift()   **removes first element
    appt{i}.conflictswith()=list

for (i=1,i<=n,i++)
{   number=n
    done=false
    while(done=false)
        {if (number>i)
            {if (appt(i).endtime() < appt(number).startime())
                {appt{i}.conflictswith().pop()}
             else
                {done=true}
             number--
             }
        else
            {done=true}
        }
}
for (i=1,i<=n,i++)
    print "Appointment ",i," conflicts with:",appt{i}.conflictswith()  

Answer 3

La solución general a este problema no es posible en O ( n ).

Como mínimo, debe ordenar por hora de inicio de cita, que requiere O ( n log n ).

Hay una solución O ( n ) si la lista ya está ordenada . El algoritmo básicamente implica verificar si la próxima cita se solapa con las anteriores. Hay un poco de sutileza en esto, ya que realmente necesita dos punteros en la lista a medida que lo ejecuta:

• La cita actual está siendo revisada
• La cita con la última hora de finalización encontrada hasta el momento (que podría no ser la cita previa)

Las soluciones O ( n ) para el caso sin clasificar solo podrían existir si tiene otras restricciones , por ejemplo, un número fijo de intervalos de tiempo de citas. Si este fue el caso, entonces puede usar HashSets para determinar qué cita (s) cubre cada intervalo de tiempo, algoritmo aproximadamente de la siguiente manera:

• Cree un HashSet para cada intervalo de tiempo - O (1) ya que el número de intervalo de tiempo es una constante fija
• Para cada cita, almacene su número de ID en HashSets de las ranuras que cubre - O ( n ) ya que la actualización de un número constante de ranuras de tiempo es O (1) para cada cita
• Ejecutar a través de las ranuras, verificando superposiciones - O (1) (o O ( n ) si desea iterar sobre las citas superpuestas para devolverlas como resultados)

Answer 4

Suponiendo que tiene alguna restricción sobre los tiempos de inicio y finalización, y sobre la resolución con la que realiza la programación, parece que sería bastante fácil convertir cada cita en un mapa de bits de veces que usa / no usa, luego haga un tipo de conteo (también conocido como tipo de cubo) en las ranuras en uso. Dado que ambos son lineales, el resultado debe ser lineal (aunque si estoy pensando correctamente, debe ser lineal en el número de intervalos de tiempo en lugar de la cantidad de citas).

Al menos si pregunté esto como una pregunta de entrevista, lo principal que esperaría es que el candidato pregunte acerca de esas restricciones (es decir, si esas restricciones están permitidas). Dado el grado en que no es realista programar citas para 1000 años a partir de ahora, o programar con una precisión de incluso un minuto (sin mencionar algo así como un nanosegundo), me parecen restricciones razonables, pero debe preguntar antes de asumirlas.

Answer 5

Un enfoque ingenuo podría ser construir dos árboles paralelos, uno ordenado por el punto inicial, y uno ordenado por el punto final de cada intervalo. Esto permite descartar la mitad de cada árbol en el tiempo O (log n), pero los resultados deben fusionarse, lo que requiere O (n) tiempo. Esto nos da consultas en O (n + log n) = O (n).