Entrevista técnica: ¿Cómo intersectar dos listas de intervalos ordenadas?

Problema y contexto aplicable

Usted recibe los arreglos A y B. Cada elemento es un intervalo cerrado [start, end]; ambos arreglos están ordenados por start no decreciente, y los intervalos dentro de un mismo arreglo no se solapan. Devuelva cada intervalo cubierto por ambas listas, también ordenado por inicio.

Para A = [[1,5],[10,14]] y B = [[2,3],[4,12]], las intersecciones son [[2,3],[4,5],[10,12]]. Los puntos extremos iguales cuentan, por lo que [1,2] y [2,4] se intersectan en [2,2].

Qué está evaluando el entrevistador

El entrevistador quiere ver si transforma dos secuencias ordenadas en un recorrido monotónico de dos punteros en lugar de comparar cada par. Una respuesta sólida define la semántica de intervalos cerrados, calcula max(start) y min(end), y demuestra por qué solo se puede descartar el intervalo con el extremo final más temprano.

Aclaraciones antes de codificar

1. ¿Los intervalos son cerrados o semiabiertos? Esto cambia si los puntos extremos iguales producen una salida.
2. ¿Ambas listas están ordenadas y son disjuntas internamente? Si no es así, ordénelas o fusione cada lista primero.
3. ¿La entrada puede estar vacía, contener intervalos puntuales o contener start > end? Esto determina la validación.
4. ¿Se deben conservar las intersecciones de longitud cero? Este problema las conserva porque los intervalos son cerrados.

Estructura de respuesta en 30 segundos

“Mantengo los punteros i y j. La intersección actual comienza en el inicio mayor y termina en el final menor; la emito cuando el punto extremo izquierdo no es mayor que el punto extremo derecho. Luego avanzo el intervalo con el final menor, porque los inicios posteriores no pueden solapar un intervalo que ya ha terminado. Si los finales coinciden, avanzo ambos. Cada puntero se mueve a través de su lista una vez, por lo que el recorrido es O(m+n) con espacio de trabajo O(1) aparte de la salida.”

Análisis paso a paso

Paso 1: Fijar la semántica de los intervalos

Trate cada intervalo como [start,end]. Sean left = max(A[i].start, B[j].start) y right = min(A[i].end, B[j].end). Existe una intersección cuando el punto extremo izquierdo no es mayor que el punto extremo derecho; los puntos extremos iguales forman un punto válido.

Paso 2: Deducir el movimiento de punteros

Si A[i].end es menor que B[j].end, A[i] termina primero. Cada intervalo posterior en B comienza no antes de B[j], por lo que A[i] no puede intersectar a B[j+1] ni a nada posterior a este. Avance i. El caso donde B[j] termina primero es simétrico.

Paso 3: Manejar finales iguales

Cuando los finales son iguales, ninguno de los intervalos actuales tiene tiempo restante que pueda solaparse con un intervalo posterior. Avance ambos punteros. Avanzar solo un lado vuelve a comprobar un intervalo agotado y puede generar comparaciones innecesarias u oscurecer la demostración.

Paso 4: Escribir un esqueleto ejecutable

function intersect(A: number[][], B: number[][]): number[][] {
  const out: number[][] = [];
  let i = 0;
  let j = 0;

  while (i < A.length && j < B.length) {
    const left = Math.max(A[i][0], B[j][0]);
    const right = Math.min(A[i][1], B[j][1]);
    if (left <= right) out.push([left, right]);

    if (A[i][1] < B[j][1]) i++;
    else if (B[j][1] < A[i][1]) j++;
    else { i++; j++; }
  }
  return out;
}

Paso 5: Declarar el invariante para la corrección

Al inicio de cada bucle, i y j identifican el par más temprano para el cual aún no se ha demostrado que no puede intersectarse. [left,right] es la única intersección posible de ese par, por lo que emitirla es completo para el par. Tras descartar el intervalo que termina antes, cada par omitido tiene un inicio posterior al de un intervalo que ya ha finalizado, por lo que no se pierde ninguna intersección.

Paso 6: Analizar la complejidad y la defensa de entradas

Los punteros solo avanzan, como máximo m+n veces, por lo que el tiempo es O(m+n). El espacio de trabajo es O(1) excluyendo la salida, u O(k) incluyendo los k intervalos emitidos. Si el ordenamiento y los puntos extremos válidos no están garantizados, valide o normalice primero; la demostración lineal no aplica a entradas arbitrarias.

Respuesta de muestra de alta calidad

Primero confirmaría que los intervalos sean cerrados, los inicios estén ordenados y no haya solapamiento dentro de ninguna de las listas. Para A[i] y B[j], la intersección utiliza el inicio mayor y el final menor; con puntos extremos cerrados, un punto extremo que no sea mayor que el otro todavía emite un punto. Luego avanzo el puntero cuyo intervalo termina primero, porque los inicios posteriores no pueden solapar un intervalo que ya ha terminado; los finales iguales avanzan ambos. Cada intervalo se procesa una vez, lo que da un tiempo O(m+n). Probaría con entradas vacías, sin solapamiento, puntos extremos iguales, intervalos puntuales, contención y varias intersecciones consecutivas.

Errores comunes

• Error → emitir solo cuando el punto extremo izquierdo es estrictamente menor → Por qué falla: la intersección de un solo punto de un intervalo cerrado desaparece → Solución: confirmar el contrato y conservar los puntos extremos iguales.
• Error → recorrer cada intervalo de B para cada intervalo de A → Por qué falla: se ignora el ordenamiento y el tiempo pasa a ser O(mn) → Solución: mantener punteros monotónicos.
• Error → incrementar siempre i → Por qué falla: B[j] puede terminar primero, provocando comparaciones repetidas o salidas omitidas → Solución: comparar los finales y avanzar el menor, ambos en caso de empate.
• Error → asegurar tiempo lineal sin una entrada ordenada → Por qué falla: la demostración de punteros deja de cumplirse → Solución: ordenar o fusionar cada lista primero.

Preguntas de seguimiento y respuestas

¿Qué cambia para intervalos semiabiertos [start,end)?

Exigir que el punto extremo izquierdo sea estrictamente menor; [1,2) y [2,4) no tienen intersección puntual. La comparación de finales para el movimiento de punteros puede permanecer igual, pero declare explícitamente el contrato de los extremos.

¿Se puede mantener O(m+n) si cada lista está desordenada y tiene solapamientos?

No directamente. Ordene y fusione cada lista primero, lo que cuesta al menos O(m log m+n log n), y luego ejecute el recorrido lineal de dos punteros.

¿Qué ocurre si la salida debe ser la longitud total de la intersección?

Mantenga el recorrido y acumule cada right-left, ajustado a la convención de los puntos extremos. Para intervalos cerrados de enteros, aclare si longitud significa la extensión geométrica o la cantidad de puntos incluidos antes de escribir la fórmula.

¿Qué sucede si las dos listas son flujos de datos (streams) que no se pueden rebobinar?

Mientras cada flujo permanezca ordenado por inicio, conserve el intervalo actual y la posición de lectura siguiente como estado del puntero. Tras emitir una intersección, descarte el intervalo que finalizó; los datos fuera de orden requieren búfer y un diseño diferente.