Sweep line

A sweep line walks along a line through the points where intervals start or end, in sorted order, and keeps track of what is open between them. It handles $n$ intervals in O(n \log n) time, however large the coordinates are. If the coordinates are small (up to about 10^6), a difference array over every unit of the line is simpler. Reach for a sweep when a problem has intervals (time periods, buildings) and the answer depends on how many, or which, are open at each place.

Explanation

Five intervals lie on a number line: A from 1 to 5, B from 3 to 7, C from 4 to 6, D from 9 to 12 and E from 11 to 14. Each one contains its left end but not its right end. How much of the line do they cover together? Adding the five lengths gives 16, but where intervals overlap (from 3 to 6 and from 11 to 12) the same part of the line is counted two or three times. The answer is 11.

A difference array solves this: mark +1 at each start and −1 at each end, take the running total over every unit of the line, and count the units above zero. But real coordinates go up to 10^9, and an array of 10^9 int cells takes 4 GB, most of them repeating their neighbour.

Fig. 1. The count of each unit under the axis. Blue ticks are starts, red ticks are ends.

Fig. 1 shows the count under the axis: the running total of the marks. It changes only at the 10 endpoints of the intervals, and between two neighbouring endpoints it is the same on every unit. So a whole gap between two endpoints can be handled at once: if its count is above zero, add its length. Only the endpoints need to be visited, in sorted order. Each endpoint is an event: a start adds 1 to the count, an end takes 1 away.

A gap lies between two events, and the count changes at both, so it matters which count measures the gap. At each event, first measure the gap since the previous event with the count it had, then apply the event. At 9, D starts. The gap from 7 to 9 has count 0, because the event at 7 closed B, so it adds nothing; only then does the count become 1.

Picture a vertical sweep line moving left to right and stopping only at events. The count is its state.

Nothing is swept yet. The count is 0 and covered is 0.

At 1, A starts. There is no gap before the first event. Now the count is 1.

At 3, B starts. The gap from 1 to 3 had count 1, so covered grows by 2 to 2. Now the count is 2.

At 4, C starts. The gap from 3 to 4 had count 2, so covered grows by 1 to 3. Now the count is 3.

At 5, A ends. The gap from 4 to 5 had count 3, so covered grows by 1 to 4. Now the count is 2.

At 6, C ends. The gap from 5 to 6 had count 2, so covered grows by 1 to 5. Now the count is 1.

At 7, B ends. The gap from 6 to 7 had count 1, so covered grows by 1 to 6. Now the count is 0.

At 9, D starts. The gap from 7 to 9 had count 0 and adds nothing. Now the count is 1.

At 11, E starts. The gap from 9 to 11 had count 1, so covered grows by 2 to 8. Now the count is 2.

At 12, D ends. The gap from 11 to 12 had count 2, so covered grows by 1 to 9. Now the count is 1.

At 14, E ends. The gap from 12 to 14 had count 1, so covered grows by 2 to 11. Now the count is 0.

1/11

Fig. 2. Step through the sweep with the buttons or the arrow keys. Blue gaps are covered, the grey outlined gap is empty.

The largest count during the walk, 3 on the gap from 4 to 5, is the largest overlap: the most intervals that share one point. And the count fell to 0 at 7, so the intervals form two groups, from 1 to 7 and from 9 to 14.

$n$ intervals give $2n$ events, so the running time is O(n \log n) for the sort plus $O(n)$ for the walk, with $O(n)$ memory.

Events at equal coordinates need an order. Give each event a kind and sort by the pair (x, kind), putting first whatever must already count at x. The intervals here are half-open, written [l, r): [3, 5) and [5, 7) share no point, so at 5 the end goes first. With pairs (x, -1) for an end and (x, +1) for a start, the change itself is the kind, and −1 already sorts first. Closed intervals [l, r] include both ends, so for them the start must come first: kind 0 for a start, kind 1 for an end. The covered length doesn't depend on this order (the gap between equal coordinates is 0), but the largest overlap and the groups do.

In C++

The template reads n half-open intervals [l, r) and prints the covered length and the largest overlap. Each interval gives two events in ev, (l, +1) and (r, -1); cnt counts the open intervals. The input is n, then n lines l r. The five intervals are:

5
1 5
3 7
4 6
9 12
11 14

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // fast input for large n
    cin.tie(nullptr);

    // read
    int n;
    cin >> n;

    // events
    vector<pair<long long, int>> ev;   // (x, +1) for a start, (x, -1) for an end
    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        ev.push_back({l, +1});
        ev.push_back({r, -1});
    }

    // sort
    sort(ev.begin(), ev.end());   // at equal x, -1 before +1: an end before a start

    // sweep
    long long covered = 0;
    int cnt = 0, best = 0;
    for (int i = 0; i < (int)ev.size(); i++) {
        // gap
        if (i > 0 && cnt > 0) covered += ev[i].first - ev[i - 1].first;
        // event
        cnt += ev[i].second;
        best = max(best, cnt);
    }

    cout << covered << " " << best << "\n";
}

Merged groups and length covered k times

A group of overlapping intervals opens when the count goes from 0 to 1 and closes when it returns to 0. Record the coordinate at those two moments in the // event part of the loop:

// before the loop
long long start = 0;
vector<pair<long long, long long>> groups;

        // event
        if (cnt == 0) start = ev[i].first;                        // a group opens
        cnt += ev[i].second;
        if (cnt == 0) groups.push_back({start, ev[i].first});     // the group closes

The five intervals give [1, 7) and [9, 14). Closed intervals that touch, such as [1, 4] and [4, 6], belong to one group, so for them sort starts before ends by kind, as in the next section. For the length covered at least k times, change cnt > 0 to cnt >= k in // gap.

Points as events

To find how many intervals contain each of many points, make each point a third kind of event that reads the count instead of changing it. For closed intervals, use kind 0 for a start, 1 for a point and 2 for an end, so at equal x a point sees the intervals that start there and those that end there. For half-open intervals, use 0 for an end, 1 for a start and 2 for a point.

vector<array<long long, 3>> ev;   // (x, kind, id): closed intervals, kind 0 start, 1 point, 2 end
for (int i = 0; i < n; i++) {
    ev.push_back({l[i], 0, i});
    ev.push_back({r[i], 2, i});
}
for (int j = 0; j < m; j++)
    ev.push_back({p[j], 1, j});
sort(ev.begin(), ev.end());

int cnt = 0;
for (auto [x, kind, id] : ev) {
    if (kind == 0) cnt++;
    else if (kind == 2) cnt--;
    else ans[id] = cnt;           // a point reads the count
}

With m points the sort takes O((n + m) \log(n + m)).

A set as the state

When a gap needs more than a count, keep the open intervals in a structure. In the skyline problem, each interval [l, r) is a building of height h, and the area under the outline is wanted. The state is a multiset of open heights, because two open buildings can have the same height, and a gap adds its length times the largest of them. Fig. 3 shows three buildings, [1, 5) of height 2, [3, 8) of height 4 and [6, 10) of height 1, and under them the multiset after each event. At 5 it holds only 4, so the gap from 5 to 6 adds 1 × 4.

Fig. 3. The open heights after each event and what each gap adds. The total is 26.

vector<array<long long, 3>> ev;   // (x, +1 or -1, height)
for (int i = 0; i < n; i++) {
    long long l, r, height;
    cin >> l >> r >> height;
    ev.push_back({l, +1, height});
    ev.push_back({r, -1, height});
}
sort(ev.begin(), ev.end());

multiset<long long> h;            // heights of the open buildings
long long area = 0;
for (int i = 0; i < (int)ev.size(); i++) {
    // gap
    if (i > 0) {
        long long tallest = h.empty() ? 0 : *h.rbegin();
        area += (ev[i][0] - ev[i - 1][0]) * tallest;
    }
    // event
    if (ev[i][1] == +1) h.insert(ev[i][2]);
    else h.erase(h.find(ev[i][2]));          // erase one copy of the height
}

Each insert and erase takes O(\log n), so the sweep stays O(n \log n). With coordinates and heights up to 10^9 the area can reach 2 \cdot 10^{18}, which still fits in long long.

Common mistakes

• Assuming l < r when a problem gives the endpoints in any order. With [1, 5) and [3, 7) entered as 1 5 and 7 3, the end at 3 comes before its start, the count goes negative, and the template prints 2 1 instead of 6 2. Swap l and r when l > r before making the events.

• Sorting ends first for closed intervals. [1, 4] and [4, 6] share the point 4, but a plain pair sort gives the largest overlap 1 instead of 2. Sort starts first by kind, or, with integer coordinates, push the end at r + 1.

• Removing a height with h.erase(height). In a multiset this removes every copy: buildings [1, 6) and [2, 4) of height 3 give an area of 9 instead of 15. Write h.erase(h.find(height)).

Similar techniques

A difference array puts the same marks into an array over every unit of the line. It is simpler when the coordinates are small and gives the count of every unit.

Sorting events in time order finds only the largest overlap and measures no gaps.

Coordinate compression replaces huge coordinates by their places in sorted order, so that an array or a tree can index them. A sweep uses it when the state needs such a structure.

A segment tree is the state of a two-dimensional sweep (the area of a union of rectangles) and handles intervals that are added and removed between questions.

Practice