¿Qué es un algoritmo para calcular el número de intervalos superpuestos?

Answer 1

Definamos la clase de intervalo como:

intervalo de clases {
int start;
int end;

Intervalo público (); // define tu constructor aquí
}

Ahora, suponga que tiene 10 intervalos de este tipo y desea fusionar los intervalos superpuestos. El algoritmo para esto es el siguiente:

Ordene los intervalos wrt al valor “inicial”;
int cuenta = 0; (no de intervalos superpuestos)
Definir una lista de arrayl (res) para mantener los nuevos intervalos
Digamos que su preStart = inicio actual (del primer intervalo) y preEnd = final (del primer intervalo)

Ahora, itere de i = 1 a len (conjunto de intervalos original)

Compare, start_i con preEnd (paso 3), si start_i es mayor que, es decir, sin superposición. Por lo tanto, ponga (preStart, preEnd to the “res”) y reasigne, preStart = start_i y preEnd = end_i

Más,

Encuentre el punto final, preEnd = Math.max (preEnd, end_i).
recuento ++;

Después, finaliza la iteración, solo vuelve a poner, preStart y preEnd a la “res”.

Número de intervalos superpuestos : recuento

Complejidad del tiempo:

Ordenar los intervalos (nlogn)

1. Iteraciones: O (n)

Complejidad espacial:

1. Peor caso: O (n)