Sweep Line

The idea

Many problems involve intervals or shapes spread across a line. Checking every pair is O(N²). A sweep line reduces it by moving an imaginary line across the input and processing only the moments where something changes.

Two ingredients:

1. Events — the positions where something begins or ends, sorted.
2. An active set — what the line currently intersects, updated at each event.

The insight is that nothing interesting happens between events, so only O(N) positions need examination.

Counting overlaps

Given N intervals, find the maximum number overlapping at any single point.

Each interval contributes two events: +1 where it starts, -1 where it ends. Sort by position and accumulate.

static int maxOverlap(int[][] intervals) {
    int n = intervals.length;
    int[][] events = new int[2 * n][2];      // {position, delta}

    for (int i = 0; i < n; i++) {
        events[2 * i]     = new int[]{intervals[i][0], 1};
        events[2 * i + 1] = new int[]{intervals[i][1], -1};
    }

    Arrays.sort(events, (a, b) ->
        a[0] != b[0] ? Integer.compare(a[0], b[0])
                     : Integer.compare(a[1], b[1]));   // -1 before +1 at a tie

    int active = 0, best = 0;
    for (int[] e : events) {
        active += e[1];
        best = Math.max(best, active);
    }
    return best;
}

Union of interval lengths

Given N intervals, find the total length covered by at least one.

Sort by start, then merge as you go.

static long coveredLength(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    long total = 0;
    int curStart = intervals[0][0], curEnd = intervals[0][1];

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] > curEnd) {          // gap — close the run
            total += curEnd - curStart;
            curStart = intervals[i][0];
            curEnd = intervals[i][1];
        } else {
            curEnd = Math.max(curEnd, intervals[i][1]);
        }
    }
    total += curEnd - curStart;                   // final run
    return total;
}

The total += curEnd - curStart after the loop is essential — the last run is never closed inside it. Forgetting it loses the final interval, which is easy to miss because the answer is otherwise plausible.

Math.max on curEnd handles a fully-nested interval, which would otherwise shrink the run.

Area of a union of rectangles

The classic two-dimensional sweep. Move a vertical line left to right; each rectangle contributes an event where it enters and one where it leaves. Between consecutive events, the covered vertical extent is constant, so the area contributed is that extent times the horizontal distance.

static long unionArea(int[][] rects) {           // {x1, y1, x2, y2}
    int n = rects.length;
    int[][] events = new int[2 * n][4];          // {x, delta, y1, y2}

    for (int i = 0; i < n; i++) {
        events[2 * i]     = new int[]{rects[i][0],  1, rects[i][1], rects[i][3]};
        events[2 * i + 1] = new int[]{rects[i][2], -1, rects[i][1], rects[i][3]};
    }
    Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));

    // count[y] = how many active rectangles cover the strip starting at y
    TreeMap<Integer, Integer> active = new TreeMap<>();
    long area = 0;
    int prevX = events[0][0];

    for (int[] e : events) {
        int x = e[0];
        area += (long) coveredY(active) * (x - prevX);
        prevX = x;

        active.merge(e[2], e[1], Integer::sum);
        active.merge(e[3], -e[1], Integer::sum);
    }
    return area;
}

// total y-length covered at least once, from the running deltas
static long coveredY(TreeMap<Integer, Integer> active) {
    long covered = 0;
    int depth = 0;
    Integer prev = null;
    for (Map.Entry<Integer, Integer> en : active.entrySet()) {
        if (depth > 0 && prev != null) covered += en.getKey() - prev;
        depth += en.getValue();
        prev = en.getKey();
    }
    return covered;
}

This version is O(N²) because coveredY rescans the active set at every event. That is fine for N up to a few thousand and is much easier to get right.

For larger N, replace the TreeMap scan with a segment tree over compressed y-coordinates that tracks how much of the range is covered, giving O(N log N). That is a genuinely harder implementation; reach for it only when the constraints demand it.

Coordinate compression

Coordinates are often up to 10⁹ while only 2N distinct values appear. Mapping them to 0..2N-1 lets you index arrays by coordinate.

int[] xs = /* every x coordinate that appears */;
int[] sorted = xs.clone();
Arrays.sort(sorted);
int m = 0;
for (int i = 0; i < sorted.length; i++) {          // deduplicate in place
    if (i == 0 || sorted[i] != sorted[i - 1]) sorted[m++] = sorted[i];
}
// index of a value v:
int idx = Arrays.binarySearch(sorted, 0, m, v);

This is a prerequisite for any array- or segment-tree-based sweep on large coordinates.

Sweep-line problem shapes

Related