Hard · sorting + sweep

Merge Intervals

Merging intervals in arrival order is chaos — the next interval may reach anywhere. Sort them by left endpoint and the world becomes a line you walk once, carrying a single running end.

At a glanceBubble-sort by left endpoint, then sweep: if the next interval starts at or before the current end, extend the end to the max of both right endpoints; otherwise emit the finished interval and start a new one.

Problem

Input: The first line is n (1 ≤ n ≤ 100). Then n lines, each with integers l and r (−1000 ≤ l ≤ r ≤ 1000): one closed interval per line, in any order.

Output: The merged intervals, one l r pair per line, sorted by left endpoint. Touching intervals (one ends where the next begins) count as overlapping and must merge.

Samples:

Input	Output
`4 1 3 2 6 8 10 15 18`	`1 6 8 10 15 18`
`2 1 4 4 5`	`1 5`

These are closed intervals: [1,4] and [4,5] share the point 4, so they fuse into [1,5]. If your code uses l < end instead of l <= end, exactly these cases will silently come out unmerged.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Sort pairs, not one array

Reordering l[] alone scrambles the data — each left endpoint drags its right endpoint with it. In a bubble sort that means: when you swap l[j] and l[j+1], swap r[j] and r[j+1] too. You already wrote this machine in Bubble Sort; here it sorts two parallel arrays as one.

Hint 2 — One running end is the whole sweep

Walk the sorted intervals keeping curL, curR — the interval you are currently growing. If the next one starts at or before curR, they overlap: set curR = max(curR, nextR) (max, because a nested interval must not shrink the end). Otherwise the current one is finished: print it and adopt the next as the new current.

Hint 3 — The last interval lives after the loop

The sweep only prints an interval when it meets a successor that does not overlap. Nobody follows the last one — so after the loop ends, print curL curR one final time. Forgetting this line is the classic symptom: output always one interval short.

Solution (try it first!)

#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;
}

Sort-then-sweep is one of the half-dozen patterns that solve most interval and event problems: calendar overlap, meeting rooms, signal ranges. The sorting you reused came from Bubble Sort; when n grows past a thousand you will swap in a faster sort and keep this exact sweep unchanged — which is the sign of a pattern, not a trick.

Deep dive

Why this works

Sorting by left endpoint turns an arbitrary pile into a line where overlap is local: each interval can only meet the one you are currently growing. One running pair (curL, curR) then sweeps once — extend on overlap (curR = max(curR, r)), emit and restart on a gap. Sort first is what converts a search problem into a scan.

The cost

O(n²) for the bubble sort and O(n) for the sweep — fine for n ≤ 100. With a real sort the whole thing is O(n log n); the sweep itself never grows.

Where it goes wrong

Sorting l[] without dragging r[] along — the rights stay home and every merge after the first is garbage. Two parallel arrays must swap together.
Using l < curR instead of l <= curR: closed intervals that touch at one point ([1,4] and [4,5]) must fuse, and this sign is exactly the case that decides it.
Forgetting the final cout << curL << " " << curR after the loop — the sweep only prints on a gap, and nothing follows the last interval.

Next step

The sort you reused is Bubble Sort. The same sort-first-then-sweep skeleton runs meeting-room and calendar-overlap problems — only the merge condition changes.

Two things to remember

Sort by left endpoint, then one sweep with a running end — that is the whole idea.
Parallel arrays swap together; the last interval prints after the loop.

🐞 This version fails — open it and try

Sorts the left endpoints but leaves the right ones at home — the pairs are scrambled

#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;
}