Posible pregunta de la entrevista: cómo encontrar todos los intervalos superpuestos

No es una pregunta de entrevista per se , ya que me encontré con esto en mi proyecto, pero pensé que podría ser una pregunta decente para intervenir.

Tienes N pares de intervalos, digamos enteros. Se requiere que identifique todos los intervalos que se superponen entre sí en el tiempo O (N). Por ejemplo, si tiene

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

la respuesta es {1, 3}, {12, 14}, {2, 4}, {13, 15}. Tenga en cuenta que no necesita agruparlos, por lo que el resultado puede ser en cualquier orden como en el ejemplo.

Acabo de arrojar O (N) tiempo porque el algoritmo KMP toma O (N) para la búsqueda de cadenas. :RE

Lo mejor que se me ocurrió y lo que estoy usando en este momento en el proyecto es O (N ^ 2). Sí, la fuerza bruta es bastante triste, pero nadie se queja, así que no la refacturaré. : P Aún así, tenía curiosidad si una mente más grande tiene una solución más elegante.

Coloque los puntos finales de los intervalos en una matriz, marcándolos como puntos iniciales o finales. Clasifíquelos rompiendo vínculos al colocar puntos finales antes de los puntos de inicio si los intervalos están cerrados, o al revés si están medio abiertos.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E 

A continuación, repita la lista y realice un seguimiento de la cantidad de intervalos en los que nos encontramos (esto equivale a la cantidad de puntos de inicio procesados ​​menos el número de puntos finales). Cada vez que alcanzamos un punto de inicio cuando ya estamos en un intervalo, esto significa que debemos tener intervalos superpuestos.

 1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E ^ ^ overlap overlap 

Podemos encontrar qué intervalos se superponen con el almacenamiento de datos junto a los puntos finales y el seguimiento de los intervalos en los que nos encontramos.

Esta es una solución O (N logN), siendo la clasificación el principal factor.

Ordenar los intervalos por punto de inicio. Luego doble sobre esta lista, fusionando cada intervalo con su vecino (es decir, (1,4), (2,6) -> (1,6)) si se superponen. La lista resultante contiene esos intervalos sin socios superpuestos. Filtra estos fuera de la lista original.

Esto es lineal en el tiempo después de la operación de clasificación inicial que podría hacerse con cualquier algoritmo (n log n). No estoy seguro de cómo te las arreglarías. Incluso la operación ‘filtrar duplicados’ al final es lineal si aprovecha el orden ya ordenado de la entrada y salida de la primera operación.

Aquí hay una implementación en Haskell:

 -- Given a list of intervals, select those which overlap with at least one other inteval in the set. import Data.List type Interval = (Integer, Integer) overlap (a1,b1)(a2,b2) | b1 < a2 = False | b2 < a1 = False | otherwise = True mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2) sortIntervals::[Interval]->[Interval] sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2)) sortedDifference::[Interval]->[Interval]->[Interval] sortedDifference [] _ = [] sortedDifference x [] = x sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys | x < y = x:(sortedDifference xs (y:ys)) | y < x = sortedDifference (x:xs) ys groupIntervals::[Interval]->[Interval] groupIntervals = foldr couldCombine [] where couldCombine next [] = [next] couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs | otherwise = next:x:xs findOverlapped::[Interval]->[Interval] findOverlapped intervals = sortedDifference sorted (groupIntervals sorted) where sorted = sortIntervals intervals sample = [(1,3),(12,14),(2,4),(13,15),(5,10)] 

El enfoque estándar para los problemas de intervalos en la línea es clasificarlos según el punto de partida y luego caminar desde el principio hasta el final. O(n*logn) ( O(n) si ya está ordenado)

 end = 0; for (current in intervals) { if current.start < end { // there's an intersection! // 'current' intersects with some interval before it ... } end = max(end, current.end) } 

No estoy seguro acerca de O (N), pero qué pasa si primero los clasificamos por el primer número en cada tupla, y luego encontramos secuencialmente aquellos en los que el primer número de la tupla es mayor que el del mayor número visto en las tuplas anteriores, que también lo hacen no se superponen con la siguiente tupla.

Entonces, primero obtendrías:

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

ya que 4 (más grande) <5 y 10 <12, {5, 10} están aislados.

Esto implicaría que hacemos un seguimiento del número más grande que encontramos, y cada vez que encontramos una tupla cuyo número de inicio es mayor, verificamos si se superpone con el siguiente.

Esto se vuelve dependiente de la eficiencia del algoritmo de clasificación, porque el último proceso sería O (N)

Supongamos que la diferencia entre los puntos de inicio y final es pequeña, digamos <32. ej. 1..32. Entonces cada intervalo se puede escribir como un patrón de bits en una palabra de 32 bits. por ejemplo [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110 . Dos intervalos, o combinaciones de intervalos, se superponen si su AND bit no es cero. p.ej. [1,2] superpone [1,3] porque 001&011 == 001 , distinto de cero. O (n) alg es mantener un funcionamiento en bits OR de intervalos vistos hasta ahora y AND cada uno nuevo:

 bitsSoFar = 0 for (n=0; n < bitPatterns.length; n++) if (bitPatterns[n] & bitsSoFar != 0) // overlap of bitPatterns[n] with an earlier pattern bitsSoFar |= bitPatterns[n] 

A la izquierda como ejercicio:

  • modificar el algoritmo para identificar también la superposición de un patrón de bits con uno posterior

  • resolver el patrón de bits para un intervalo en O (1)

Si N pares de intervalos son enteros, entonces podemos obtenerlo en O (n).

Ordenarlo por el primer número del par y luego el segundo número. Si todos son enteros, podemos usar el ordenamiento del cubo o la clasificación del radix para obtenerlo por O (n).

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

Luego combine uno por uno,

{1,3}

{1,4} con superposición {1,3} y {2,4}

{1,4}, {5,10}

{1,4}, {5,10}, {12,14}

{1,4}, {5,10}, {12,15} con superposición {12,14} y {13,15}

La combinación tomaría O (N) tiempo

Este problema se puede reducir al problema de exclusividad del elemento.

La unicidad del elemento tiene un límite inferior Omega (n log n) (contando el número de comparaciones), por lo que no se puede hacer nada mejor que eso.

Ha pasado bastante tiempo desde que lo utilicé, pero la solución que utilicé fue un derivado del árbol rojo-negro descrito en Introducción a los Algoritmos llamado árbol de intervalos. Es un árbol ordenado por inicio de intervalo, por lo que puede buscar rápidamente (búsqueda binaria) primero el primer nodo elegible. IIRC, los nodos fueron ordenados por una propiedad que le permite dejar de “caminar” el árbol cuando los nodos candidatos no coinciden con su intervalo. Entonces creo que fue O (m) búsqueda, donde m es el número de intervalos coincidentes.

La búsqueda encontró esta implementación .

Brett

[edit] Releyendo la pregunta, esto no es lo que preguntaste. Creo que esta es la mejor implementación cuando tiene una lista de reuniones (por ejemplo) ya progtwigdas en las salas de conferencias (que se agregan al árbol) y desea encontrar las salas que todavía están disponibles para una reunión con un nuevo inicio y duración (el término de búsqueda). Esperemos que esta solución tenga cierta relevancia, sin embargo.

 int find_no_overlapping_intervals(const vector< pair& a) { // a[i].first -> X ,a[i].second->Y // sort by start time sort.begin(a.begin(), a.end()); // maintain  in m map m; // i // for each point, we know its a[i].X >= a[0].X. ....a[i-1].X // there will be overlap, if for some j < i, a[j].Y >= a[i].X // lower_bound to find this.. it can be found in O(log(n)) as we use std::map for maintaining y int ans = 0; for (int i=0; i < a.begin(); i++) { auto sit = m.lower_bound(m.begin(), m.end(), a[i].first); auto eit = m.upper_bound(m.begin(), m.end(), a[i].first); for (auto it = sit; it != eit; it++) ans += it->second; m[a[i].second]++; } return ans; } 
 public ArrayList merge(ArrayList intervals) { ArrayList res = new ArrayList(); if (intervals == null || intervals.isEmpty()) return res; Comparator comparator = new Comparator() { @Override public int compare(Interval i1, Interval i2) { if (i1.start < i2.start) return -1; else if (i1.start > i2.start) return 1; else { if (i1.end < i2.end) return -1; else if (i1.end > i2.end) return 1; else return 0; } } }; Collections.sort(intervals, comparator); for (int i = 0; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (res.isEmpty()) { res.add(cur); } else { Interval last = res.get(res.size() - 1); if (last.end >= cur.start) { last.end = Math.max(last.end, cur.end); } else { res.add(cur); } } } return res; } 

Esta es una implementación O(N*log(N)) simple en Python:

 def overlapping(intervals): last = (-1, -1) overlapping = set() for curr in sorted(intervals, key=lambda p: p[0]): if curr[0] < last[1]: overlapping.add(curr) overlapping.add(last) last = max(curr, last, key=lambda p: p[1]) return list(overlapping - set((-1, -1))) print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)]) #=> [(1, 3), (13, 15), (2, 4), (12, 14)] 

Primero, ordena los intervalos al finalizar el tiempo, que para cada intervalo compara el tiempo inicial con el mayor tiempo de finalización encontrado, y si es más pequeño significa que hay una superposición.

La parte de clasificación es la que requiere más tiempo, por lo que la complejidad final es N*log(N) .

Implementación en C ++ utilizando un algoritmo de línea de barrido ( O(N log N) ):

 #include  #include  #include  #include  #include  struct Interval { double start; double end; }; //----------------------------------------------------------------------------- // Enum to qualify event: Start/End of "segment-line" enum class EIntervalState { Start, End }; //----------------------------------------------------------------------------- // Events used for collision detection struct Event { double pos; EIntervalState state; std::size_t id; }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should overlap class LessIncludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, lhs.state) < std::tie(rhs.pos, rhs.state); } }; //----------------------------------------------------------------------------- // Comparator to use if {1, 2} and {2, 3} should not overlap class LessExcludeLimit { public: bool operator()(const Event& lhs, const Event& rhs) const { return std::tie(lhs.pos, rhs.state) < std::tie(rhs.pos, lhs.state); } }; //----------------------------------------------------------------------------- std::vector MakeEvents(const std::vector& intervals) { std::vector res; std::size_t id = 0; for (const auto& interval : intervals) { res.push_back({interval.start, EIntervalState::Start, id}); res.push_back({interval.end, EIntervalState::End, id}); ++id; } return res; } //----------------------------------------------------------------------------- template  std::vector> ComputeOverlappingIntervals(std::vector&& events, Less less) { std::sort(events.begin(), events.end(), less); std::set activeIds; std::vector> res; for (const auto& event : events) { switch (event.state) { case EIntervalState::Start: { for (const auto& id : activeIds) { res.emplace_back(std::minmax(event.id, id)); } activeIds.emplace(event.id); break; } case EIntervalState::End: { activeIds.erase(event.id); break; } } } return res; } 

Y úsala:

 int main() { const std::vector intervals = { {1, 3}, {12, 14}, {2, 4}, {13, 15}, {5, 10} }; for (const auto& p : ComputeOverlappingIntervals(MakeEvents(intervals), LessExcludeLimit{})) { std::cout << "intervals " << p.first << " and " << p.second << " overlap\n"; } } 

Manifestación

Aquí hay una implementación O(N lg N) en Java que extiende la respuesta proporcionada por @Nikita Rybak.

Mi solución encuentra que cada intervalo se superpone con al menos otro intervalo y los cuenta como intervalos superpuestos. Por ejemplo, los dos intervalos (1, 3) y (2, 4) de la pregunta original de OP se superponen entre sí, por lo que en este caso hay 2 intervalos superpuestos. En otras palabras, si el intervalo A se solapa con el intervalo B, entonces agrego tanto A como B al conjunto resultante de intervalos que se superponen.

Ahora considere los intervalos (1, 100) , (10, 20) y (30, 50) . Mi código encontrará que:

 [ 10, 20] overlaps with [ 1, 100] [ 30, 50] overlaps with [ 1, 100] Resulting intervals that overlap with at least one other interval: [ 1, 100] [ 30, 50] [ 10, 20] 

Para evitar que (1, 100) se cuente dos veces, utilizo un Set Java que solo conserva objetos de intervalo únicos.

Mi solución sigue este esquema.

  1. Ordene todos los intervalos por punto de inicio. Este paso es O(N lg N) .
  2. Mantenga un registro de intervalWithLatestEnd , el intervalo con el último punto final.
  3. Iterate sobre todos los intervalos en la lista ordenada. Si un intervalo se solapa con intervalWithLatestEnd , agregue ambos a un conjunto. Actualice intervalWithLatestEnd cuando sea necesario. Este paso es O(N) .
  4. Devuelva el conjunto (y conviértalo en una lista si es necesario).

El tiempo total de ejecución es O(N lg N) . Requiere un conjunto de salida de tamaño O(N) .

Implementación

Para agregar intervalos a un conjunto, creé una clase de Intervalo personalizada que anula equals() , como se esperaba.

 class Interval { int start; int end; Interval(int s, int e) { start = s; end = e; } @Override public String toString() { return String.format("[%3d, %3d]", start, end); } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + start; result = prime * result + end; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; final Interval other = (Interval) obj; if (start != other.start) return false; if (end != other.end) return false; return true; } } 

Y aquí está el código que ejecuta el algoritmo:

 private static List findIntervalsThatOverlap(List intervals) { // Keeps unique intervals. Set set = new HashSet(); // Sort the intervals by starting time. Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start)); // Keep track of the interval that has the latest end time. Interval intervalWithLatestEnd = null; for (Interval interval : intervals) { if (intervalWithLatestEnd != null && interval.start < intervalWithLatestEnd.end) { // Overlap occurred. // Add the current interval and the interval it overlapped with. set.add(interval); set.add(intervalWithLatestEnd); System.out.println(interval + " overlaps with " + intervalWithLatestEnd); } // Update the interval with latest end. if (intervalWithLatestEnd == null || intervalWithLatestEnd.end < interval.end) { intervalWithLatestEnd = interval; } } // Convert the Set to a List. return new ArrayList(set); } 

Casos de prueba

Aquí hay un caso de prueba que ejecuta los intervalos originales de OP:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); intervals.add(new Interval(1, 3)); intervals.add(new Interval(12, 14)); intervals.add(new Interval(2, 4)); intervals.add(new Interval(13, 15)); intervals.add(new Interval(5, 10)); result = findIntervalsThatOverlap(intervals); System.out.println("Intervals that overlap with at least one other interval:"); for (Interval interval : result) { System.out.println(interval); } } 

con el resultado:

 [ 2, 4] overlaps with [ 1, 3] [ 13, 15] overlaps with [ 12, 14] Intervals that overlap with at least one other interval: [ 2, 4] [ 1, 3] [ 13, 15] [ 12, 14] 

Finalmente, aquí hay un caso de prueba más avanzado:

 public static void testcase() { List intervals = null; List result = null; intervals = new ArrayList(); intervals.add(new Interval(1, 4)); intervals.add(new Interval(2, 3)); intervals.add(new Interval(5, 7)); intervals.add(new Interval(10, 20)); intervals.add(new Interval(15, 22)); intervals.add(new Interval(9, 11)); intervals.add(new Interval(8, 25)); intervals.add(new Interval(50, 100)); intervals.add(new Interval(60, 70)); intervals.add(new Interval(80, 90)); result = findIntervalsThatOverlap(intervals); System.out.println("Intervals that overlap with at least one other interval:"); for (Interval interval : result) { System.out.println(interval); } } 

con el resultado:

 [ 2, 3] overlaps with [ 1, 4] [ 9, 11] overlaps with [ 8, 25] [ 10, 20] overlaps with [ 8, 25] [ 15, 22] overlaps with [ 8, 25] [ 60, 70] overlaps with [ 50, 100] [ 80, 90] overlaps with [ 50, 100] Intervals that overlap with at least one other interval: [ 2, 3] [ 8, 25] [ 9, 11] [ 50, 100] [ 1, 4] [ 15, 22] [ 10, 20] [ 60, 70] [ 80, 90] 

Puede revisar la lista una vez y mantener una tabla hash de todos los intervalos encontrados hasta el momento. Si un intervalo de entrada es parte de algún intervalo de la tabla hash, combínelo en el intervalo de la tabla hash. Marque los intervalos no primitivos (intervalos combinados que consisten en más de un intervalo).

Luego revisa la lista por segunda vez, y para cada intervalo, compruebe en la tabla hash si está contenida en un intervalo combinado o no.

No sé si es O (N), pero es mucho mejor que O (N ^ 2).