Difícil · ordenar y barrer

Fusionar intervalos

Fusionar intervalos en orden de llegada es caos — el siguiente puede llegar a cualquier parte. Ordénalos por extremo izquierdo y el mundo se vuelve una línea que recorres una vez, cargando un único extremo corriente.

En una fraseOrdena por extremo izquierdo y barre: si el siguiente empieza antes o en el extremo actual, extiende el extremo al mayor de los dos derechos; si no, emite el intervalo cerrado y abre otro.

El problema

Entrada: La primera línea es n (1 ≤ n ≤ 100). Luego n líneas, cada una con los enteros l y r (−1000 ≤ l ≤ r ≤ 1000): un intervalo cerrado por línea, en cualquier orden.

Salida: Los intervalos fusionados, un par l r por línea, ordenados por extremo izquierdo. Los intervalos que se tocan (uno acaba donde empieza el otro) cuentan como solapados y deben fusionarse.

Ejemplos:

Entrada	Salida
`4 1 3 2 6 8 10 15 18`	`1 6 8 10 15 18`
`2 1 4 4 5`	`1 5`

Son intervalos cerrados: [1,4] y [4,5] comparten el punto 4, así que se funden en [1,5]. Si tu código usa l < end en lugar de l <= end, justo estos casos saldrán sin fusionar, sin avisar.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Ordena parejas, no un array

Reordenar l[] solo revuelve los datos — cada extremo izquierdo arrastra el suyo derecho. En un burbuja significa: cuando intercambias l[j] y l[j+1], intercambia también r[j] y r[j+1]. Esta máquina ya la escribiste en Ordenamiento burbuja; aquí ordena dos arrays paralelos como uno.

Pista 2 — Un extremo corriente es todo el barrido

Recorre los intervalos ordenados llevando curL, curR — el intervalo que estás haciendo crecer. Si el siguiente empieza antes o en curR, se solapan: pon curR = max(curR, nextR) (max, porque uno contenido no debe encoger el extremo). Si no, el actual está terminado: escríbelo y adopta el siguiente como corriente.

Pista 3 — El último intervalo vive después del bucle

El barrido solo escribe un intervalo cuando encuentra un sucesor que no solapa. Tras el último no hay nadie — así que, al terminar el bucle, escribe curL curR una vez más. Olvidar esa línea es el síntoma clásico: la salida siempre va un intervalo corta.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int l[105], r[105];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                int tl = l[j]; l[j] = l[j + 1]; l[j + 1] = tl;
                int tr = r[j]; r[j] = r[j + 1]; r[j + 1] = tr;
            }
        }
    }

    int curL = l[0], curR = r[0];
    for (int i = 1; i < n; i++) {
        if (l[i] <= curR) {
            if (r[i] > curR) curR = r[i];
        } else {
            cout << curL << " " << curR << endl;
            curL = l[i];
            curR = r[i];
        }
    }
    cout << curL << " " << curR << endl;
    return 0;
}

Ordenar-y-barrer es uno de los media patrón que resuelven casi todos los problemas de intervalos y eventos: solapes de agenda, salas de reuniones, rangos de señal. El ordenamiento que reutilizaste viene de Ordenamiento burbuja; cuando n pase de mil cambiarás a uno más rápido y este barrido quedará intacto — ahí está la señal de un patrón, no de un truco.

Análisis profundo

Por qué funciona

Ordenar por extremo izquierdo convierte un montón arbitrario en una línea donde el solape es local: cada intervalo solo puede cruzarse con el que estás haciendo crecer. Un par corriente (curL, curR) barre una vez — extiende si solapa (curR = max(curR, r)), emite y reinicia si hay hueco. Ordenar primero es lo que convierte una búsqueda en un barrido.

El coste

O(n²) para la burbuja y O(n) para el barrido — de sobra para n ≤ 100. Con un ordenamiento real todo queda en O(n log n); el barrido en sí nunca crece.

Dónde falla

Ordenar l[] sin arrastrar r[] — los derechos se quedan en casa y toda fusión posterior al primer cruce es basura. Dos arrays paralelos deben intercambiarse juntos.
Usar l < curR en vez de l <= curR: los intervalos cerrados que se tocan en un punto ([1,4] y [4,5]) deben fundirse, y ese signo es exactamente quien lo decide.
Olvidar el cout << curL << " " << curR final tras el bucle — el barrido solo escribe al encontrar un hueco, y tras el último intervalo no hay hueco.

Siguiente paso

El ordenamiento que reutilizaste es Ordenamiento burbuja. El mismo esqueleto de ordenar-y-barrer resuelve salas de reuniones y solapes de agenda — solo cambia la condición de fusión.

Dos cosas para recordar

Ordena por extremo izquierdo y barre una vez con un extremo corriente — toda la idea.
Los arrays paralelos se intercambian juntos; el último intervalo se escribe tras el bucle.

🐞 Esta versión falla: ábrela y pruébala

Ordena los extremos izquierdos pero deja los derechos en casa: las parejas quedan revueltas

#include <iostream>
using namespace std;

int l[105], r[105];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i];
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (l[j] > l[j + 1]) {
                int t = l[j]; l[j] = l[j + 1]; l[j + 1] = t;
                // bug: r[] never swaps — pairs are broken
            }
        }
    }
    int curL = l[0], curR = r[0];
    for (int i = 1; i < n; i++) {
        if (l[i] <= curR) { if (r[i] > curR) curR = r[i]; }
        else { cout << curL << " " << curR << endl; curL = l[i]; curR = r[i]; }
    }
    cout << curL << " " << curR << endl;
    return 0;
}