22.07Intermediate4 topics20 min3 interactive animations

Combined techniques

Sweep line combined with other structures: heap, Fenwick tree, segment tree and offline queries ordered by right endpoint.

Learning goals

Pair a sweep with a heap to schedule events by deadline
Count crossings with a sweep and a Fenwick tree
Compute the area of a union of rectangles with a sweep and a segment tree
Answer range queries offline by sorting them by right endpoint

Prerequisites

One-dimensional sweep lineCoordinate compressionHeaps and priority queues

A sweep decides the order in which things are seen; the companion structure answers the question about what has been seen. Most hard interval and geometry problems are one of these pairings.

22.07.1

Sweep + heap

A sweep that needs 'the active object that ends first' pairs naturally with a **min-heap of end times**. The meeting-rooms algorithm is the clearest example: sweep meetings in start order and reuse the room whose meeting ends earliest. The heap size is the number of rooms at any moment.

The same pattern solves 'attend the most events', where each event can be attended on any single day from its start to its end: sweep the days, push the end days of events that have started, drop expired ones and attend the event that ends soonest. Attending the soonest-deadline event first is the same greedy choice as earliest-deadline-first from the previous chapter.

Java

1// events[i] = {startDay, endDay} inclusive; one event per day; returns the most events that can be attended
2static int maxEvents(int[][] events) {
3    int[][] a = events.clone();
4    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
5    PriorityQueue<Integer> ends = new PriorityQueue<>();
6    int i = 0, attended = 0, day = 0;
7    while (i < a.length || !ends.isEmpty()) {
8        if (ends.isEmpty()) day = a[i][0];                   // jump over idle days
9        while (i < a.length && a[i][0] <= day) ends.add(a[i++][1]);
10        while (!ends.isEmpty() && ends.peek() < day) ends.poll();   // expired
11        if (!ends.isEmpty()) { ends.poll(); attended++; }    // attend the event that ends soonest
12        day++;
13    }
14    return attended;
15}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Minimum meeting rooms (sweep sorted events)

Interactive · edit the input

t=0

meetings

[0, 30]

[5, 10]

[10, 25]

[15, 20]

[22, 28]

0123456789101112131415161718192021222324252627282930

starts (sorted)

ends (sorted)

Setup

Only the times matter, not which meeting is which. Sort starts and ends separately and sweep left to right.

Step 1 / 9

Java

1public static int minRooms(int[][] meetings) {     // [start, end), end is exclusive
2    int n = meetings.length;
3    int[] starts = new int[n], ends = new int[n];
4    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
5    Arrays.sort(starts);
6    Arrays.sort(ends);
7    int rooms = 0, best = 0, e = 0;
8    for (int s = 0; s < n; s++) {
9        while (ends[e] <= starts[s]) { e++; rooms--; }   // meetings that ended free a room
10        rooms++;
11        best = Math.max(best, rooms);
12    }
13    return best;
14}

Live state

0 events

rooms

best

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L5	rooms=0 best=0	Only the times matter, not which meeting is which. Sort starts and ends separately and sweep left to right.
2	L11	time=0 rooms=1 best=1	A meeting starts at 0: 1 room in use. Peak so far 1.
3	L11	time=5 rooms=2 best=2	A meeting starts at 5: 2 rooms in use. Peak so far 2.
4	L9	time=10 rooms=1 best=2	A meeting ended at 10 ≤ 10: its room is free again.
5	L11	time=10 rooms=2 best=2	A meeting starts at 10: 2 rooms in use. Peak so far 2.
6	L11	time=15 rooms=3 best=3	A meeting starts at 15: 3 rooms in use. Peak so far 3.
7	L9	time=22 rooms=2 best=3	A meeting ended at 20 ≤ 22: its room is free again.
8	L11	time=22 rooms=3 best=3	A meeting starts at 22: 3 rooms in use. Peak so far 3.
9	L13	return=3	3 rooms needed: the maximum number of meetings overlapping at any moment. O(n log n).

22.07.2

Sweep + Fenwick

A **Fenwick tree** (binary indexed tree) keeps counts over positions and answers prefix sums and point updates in O(log n). Combined with a sweep it replaces the linear scan over active values. In the crossing problem, store 1 at the compressed y of every active horizontal segment; a vertical segment's crossings are the count of active y-values in its range, a difference of two prefix sums.

That changes the cost of a query from the number of active y-values in its range (which can be as large as n) to O(log n), so the whole sweep is O(n log n) even when the number of crossings is huge. The animation runs the same sweep; the difference lies only in the data structure. The Fenwick tree itself is covered in the range-query chapters of the course.

Java

1// horiz[i] = {y, x1, x2}; vert[i] = {x, y1, y2}; closed segments; counts crossings in O((n + q) log n)
2static long crossingsFenwick(int[][] horiz, int[][] vert) {
3    int[] ys = Arrays.stream(horiz).mapToInt(h -> h[0]).sorted().distinct().toArray();
4    int[] tree = new int[ys.length + 1];
5    List<int[]> events = new ArrayList<>();                  // {x, kind, index}; 0 = insert, 1 = query, 2 = remove
6    for (int i = 0; i < horiz.length; i++) { events.add(new int[]{horiz[i][1], 0, i}); events.add(new int[]{horiz[i][2], 2, i}); }
7    for (int i = 0; i < vert.length; i++) events.add(new int[]{vert[i][0], 1, i});
8    events.sort((p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
9    long total = 0;
10    for (int[] e : events) {
11        if (e[1] != 1) {
12            int pos = Arrays.binarySearch(ys, horiz[e[2]][0]) + 1;       // 1-based Fenwick position
13            int delta = e[1] == 0 ? 1 : -1;
14            for (; pos <= ys.length; pos += pos & -pos) tree[pos] += delta;
15        } else {
16            int lo = lowerBound(ys, vert[e[2]][1]);                      // first y >= y1
17            int hi = lowerBound(ys, vert[e[2]][2] + 1);                  // first y > y2
18            total += prefix(tree, hi) - prefix(tree, lo);
19        }
20    }
21    return total;
22}
23
24static int lowerBound(int[] a, int v) {
25    int lo = 0, hi = a.length;
26    while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] < v) lo = mid + 1; else hi = mid; }
27    return lo;
28}
29
30static int prefix(int[] tree, int count) {                  // sum of the first 'count' positions
31    int s = 0;
32    for (int pos = count; pos > 0; pos -= pos & -pos) s += tree[pos];
33    return s;
34}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Counting crossings of horizontal and vertical segments

Interactive · edit the input

H1 y=2

[1, 6]

H2 y=4

[3, 9]

H3 y=7

[0, 4]

V1 x=3

y 0-5

V2 x=5

y 3-8

V3 x=8

y 1-9

0123456789

events by x (add, query, remove)

+H3@0

+H1@1

+H2@3

?V1@3

−H3@4

?V2@5

−H1@6

?V3@8

−H2@9

active y values

none

crossings found

none

Setup

Sweep a vertical line from left to right. A horizontal segment is active between its two end x values. When the sweep reaches a vertical segment, every active y inside its y-range is a crossing. At the same x, add first and remove last so touching ends count.

Step 1 / 11

Java

1static int crossings(int[][] horiz, int[][] vert) {            // horiz: {y, x1, x2}; vert: {x, y1, y2}
2    List<int[]> ev = new ArrayList<>();                         // {x, type, index}: 0 = add h-segment, 1 = vertical query, 2 = remove
3    for (int i = 0; i < horiz.length; i++) { ev.add(new int[]{horiz[i][1], 0, i}); ev.add(new int[]{horiz[i][2], 2, i}); }
4    for (int i = 0; i < vert.length; i++) ev.add(new int[]{vert[i][0], 1, i});
5    ev.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));   // at one x: add, query, then remove
6    TreeMap<Integer, Integer> ys = new TreeMap<>(); int count = 0;                                 // active y -> multiplicity
7    for (int[] e : ev) {
8        if (e[1] == 0) ys.merge(horiz[e[2]][0], 1, Integer::sum);
9        else if (e[1] == 2) { if (ys.merge(horiz[e[2]][0], -1, Integer::sum) == 0) ys.remove(horiz[e[2]][0]); }
10        else for (int c : ys.subMap(vert[e[2]][1], true, vert[e[2]][2], true).values()) count += c;   // active y inside the vertical range
11    }
12    return count;
13}

Live state

horizontal

vertical

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2	horizontal=3 vertical=3	Sweep a vertical line from left to right. A horizontal segment is active between its two end x values. When the sweep reaches a vertical segment, every active y inside its y-range is a crossing. At the same x, add first and remove last so touching ends count.
2	L8	x=0 event=add H3	x = 0: horizontal segment H3 (y = 7) becomes active.
3	L8	x=1 event=add H1	x = 1: horizontal segment H1 (y = 2) becomes active.
4	L8	x=3 event=add H2	x = 3: horizontal segment H2 (y = 4) becomes active.
5	L10	x=3 query=V1 y 0..5 crossings=2	Vertical V1 spans y 0 to 5: the active values 2, 4 lie inside it, so 2 crossings (total 2).
6	L9	x=4 event=remove H3	x = 4: H3 ends and leaves the active set.
7	L10	x=5 query=V2 y 3..8 crossings=3	Vertical V2 spans y 3 to 8: the active values 4 lie inside it, so 1 crossing (total 3).
8	L9	x=6 event=remove H1	x = 6: H1 ends and leaves the active set.
9	L10	x=8 query=V3 y 1..9 crossings=4	Vertical V3 spans y 1 to 9: the active values 4 lie inside it, so 1 crossing (total 4).
10	L9	x=9 event=remove H2	x = 9: H2 ends and leaves the active set.
11	L12	return=4	4 crossings. The sweep costs O((n + k) log n) for n segments and k crossings reported.

22.07.3

Sweep + segment tree

Some sweeps need to know, for the active objects, a value that changes over a range of positions, such as how much of the y-axis is covered by at least one rectangle. A **segment tree** over the compressed y-coordinates supports 'add 1 or subtract 1 on a range' and 'how much length is covered right now'. The sweep moves in x; between two consecutive x events the covered y-length is constant, so the area adds coveredLength × (x_next - x).

Each rectangle makes two events (its left edge adds coverage on [y1, y2), its right edge removes it). The segment tree node keeps a count of full covers and the covered length in its range, computed from its children unless the count is positive. Total cost is O(n log n) for n rectangles. The tree itself is the subject of a later chapter; this is the code-only application of the sweep.

Java

1// rects[i] = {x1, y1, x2, y2}, half-open; returns the area of the union
2static long unionArea(int[][] rects) {
3    int[] ys = Arrays.stream(rects).flatMapToInt(r -> IntStream.of(r[1], r[3])).sorted().distinct().toArray();
4    int m = ys.length - 1;                                   // number of elementary y-segments
5    int[] cnt = new int[4 * Math.max(m, 1)];
6    long[] len = new long[4 * Math.max(m, 1)];
7    List<int[]> events = new ArrayList<>();                  // {x, y1, y2, +1 or -1}
8    for (int[] r : rects) { events.add(new int[]{r[0], r[1], r[3], 1}); events.add(new int[]{r[2], r[1], r[3], -1}); }
9    events.sort(Comparator.comparingInt(e -> e[0]));
10    long area = 0;
11    int prevX = events.get(0)[0];
12    for (int[] e : events) {
13        area += len[1] * (e[0] - prevX);                     // covered y-length times the width since the last event
14        prevX = e[0];
15        update(1, 0, m, Arrays.binarySearch(ys, e[1]), Arrays.binarySearch(ys, e[2]), e[3], cnt, len, ys);
16    }
17    return area;
18}
19
20// segment tree over elementary segments [lo, hi): a node covers ys[lo]..ys[hi]
21static void update(int node, int lo, int hi, int ql, int qr, int delta, int[] cnt, long[] len, int[] ys) {
22    if (qr <= lo || hi <= ql) return;
23    if (ql <= lo && hi <= qr) cnt[node] += delta;
24    else {
25        int mid = (lo + hi) >>> 1;
26        update(2 * node, lo, mid, ql, qr, delta, cnt, len, ys);
27        update(2 * node + 1, mid, hi, ql, qr, delta, cnt, len, ys);
28    }
29    if (cnt[node] > 0) len[node] = ys[hi] - ys[lo];          // fully covered by some rectangle
30    else if (hi - lo == 1) len[node] = 0;
31    else len[node] = len[2 * node] + len[2 * node + 1];
32}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

22.07.4

Offline queries by right endpoint

**Offline** means all queries are known in advance, so you may answer them in any order. For 'how many distinct values in a[l..r]', sort the queries by right endpoint and sweep the array left to right. When position i is reached, add 1 at i in a Fenwick tree and, if the value occurred before at position p, remove the mark at p: after that, each distinct value in a[0..i] is marked exactly once, at its latest occurrence. A query (l, r) with r = i is then the number of marks in [l, r].

In the “Four queries” preset the array is [1, 2, 1, 3, 2, 3, 1] with queries 0-3, 2-5, 1-6 and 4-4, and the answers in input order are [3, 3, 3, 1]. The cost is O((n + q) log n) against O(n · q) for scanning each range; the animation states that comparison explicitly.

Java

1// queries[i] = {l, r} inclusive; answers[i] = number of distinct values in a[l..r]
2static int[] distinctInRanges(int[] a, int[][] queries) {
3    int n = a.length;
4    Integer[] order = new Integer[queries.length];
5    for (int i = 0; i < order.length; i++) order[i] = i;
6    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][1]));   // by right endpoint
7    int[] tree = new int[n + 1];
8    Map<Integer, Integer> last = new HashMap<>();
9    int[] answers = new int[queries.length];
10    int next = 0;
11    for (int i = 0; i < n; i++) {
12        Integer prev = last.put(a[i], i);
13        if (prev != null) add(tree, prev + 1, -1);           // the earlier occurrence no longer counts
14        add(tree, i + 1, +1);
15        while (next < order.length && queries[order[next]][1] == i) {
16            int[] q = queries[order[next]];
17            answers[order[next]] = sum(tree, q[1] + 1) - sum(tree, q[0]);
18            next++;
19        }
20    }
21    return answers;
22}
23
24static void add(int[] tree, int pos, int delta) { for (; pos < tree.length; pos += pos & -pos) tree[pos] += delta; }
25
26static int sum(int[] tree, int pos) { int s = 0; for (; pos > 0; pos -= pos & -pos) s += tree[pos]; return s; }

Best

O((n + q) log n)

Average

O((n + q) log n)

Worst

O((n + q) log n)

Space

O(n + q)

Distinct values in ranges: sweep by right endpoint + Fenwick tree

Interactive · edit the input

array

marked: latest copy of each value

Fenwick tree bit[1..n]

0bit[1]

0bit[2]

0bit[3]

0bit[4]

0bit[5]

0bit[6]

0bit[7]

answers (by query)

?0-3

?2-5

?1-6

?4-4

Setup

A range [l, r] holds as many distinct values as there are positions in it that are the LAST copy of their value among positions up to r. So sweep r from left to right, keep a 1 only on the latest copy of each value in a Fenwick tree, and answer each query ending at r with a range sum. Queries are answered offline, sorted by r.

Step 1 / 17

Java

1static int[] distinctInRanges(int[] a, int[][] queries) {         // queries[k] = {l, r}
2    int n = a.length; int[] bit = new int[n + 1], ans = new int[queries.length];
3    Integer[] order = new Integer[queries.length]; for (int k = 0; k < order.length; k++) order[k] = k;
4    Arrays.sort(order, Comparator.comparingInt(k -> queries[k][1]));     // offline: answer queries by right endpoint
5    Map<Integer, Integer> last = new HashMap<>(); int q = 0;
6    for (int i = 0; i < n; i++) {
7        Integer prev = last.put(a[i], i);
8        if (prev != null) add(bit, prev, -1);                          // the value's earlier copy no longer counts
9        add(bit, i, +1);                                               // only the latest copy of each value is marked
10        while (q < order.length && queries[order[q]][1] == i) {
11            int[] qr = queries[order[q]];
12            ans[order[q++]] = sum(bit, i) - sum(bit, qr[0] - 1);       // marked positions inside [l, r] = distinct values
13        }
14    }
15    return ans;
16}

Live state

queries

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L4	n=7 queries=4	A range [l, r] holds as many distinct values as there are positions in it that are the LAST copy of their value among positions up to r. So sweep r from left to right, keep a 1 only on the latest copy of each value in a Fenwick tree, and answer each query ending at r with a range sum. Queries are answered offline, sorted by r.
2	L9	i=0 value=1	Mark index 0, the latest copy of 1: add +1 in the Fenwick tree.
3	L9	i=1 value=2	Mark index 1, the latest copy of 2: add +1 in the Fenwick tree.
4	L8	i=2 value=1 earlier copy=0	1 already appeared at index 0: unmark that copy (add −1 there), because only the latest copy counts.
5	L9	i=2 value=1	Mark index 2, the latest copy of 1: add +1 in the Fenwick tree.
6	L9	i=3 value=3	Mark index 3, the latest copy of 3: add +1 in the Fenwick tree.
7	L12	query=[0, 3] prefix(r)=3 prefix(l-1)=0 answer=3	Query [0, 3] ends here: marked positions in it = prefix(3) − prefix(-1) = 3 − 0 = 3 distinct values.
8	L8	i=4 value=2 earlier copy=1	2 already appeared at index 1: unmark that copy (add −1 there), because only the latest copy counts.
9	L9	i=4 value=2	Mark index 4, the latest copy of 2: add +1 in the Fenwick tree.
10	L12	query=[4, 4] prefix(r)=3 prefix(l-1)=2 answer=1	Query [4, 4] ends here: marked positions in it = prefix(4) − prefix(3) = 3 − 2 = 1 distinct values.
11	L8	i=5 value=3 earlier copy=3	3 already appeared at index 3: unmark that copy (add −1 there), because only the latest copy counts.
12	L9	i=5 value=3	Mark index 5, the latest copy of 3: add +1 in the Fenwick tree.
13	L12	query=[2, 5] prefix(r)=3 prefix(l-1)=0 answer=3	Query [2, 5] ends here: marked positions in it = prefix(5) − prefix(1) = 3 − 0 = 3 distinct values.
14	L8	i=6 value=1 earlier copy=2	1 already appeared at index 2: unmark that copy (add −1 there), because only the latest copy counts.
15	L9	i=6 value=1	Mark index 6, the latest copy of 1: add +1 in the Fenwick tree.
16	L12	query=[1, 6] prefix(r)=3 prefix(l-1)=0 answer=3	Query [1, 6] ends here: marked positions in it = prefix(6) − prefix(0) = 3 − 0 = 3 distinct values.
17	L15	return=[3, 3, 3, 1]	Answers in input order: [3, 3, 3, 1]. O((n + q) log n) overall; a naive scan per query would cost O(n q).

Practice ladder

Now try it yourself

Easy

Number of Days Between Two Dates
Count Days Without Meetings

Medium

Maximum Number of Events That Can Be Attended
Meeting Rooms III
Count Number of Teams

Advanced

Rectangle Area II
Number of Flowers in Full Bloom
Range Sum Query - Mutable (offline variants)

Key takeaways

Sweep plus a heap picks the active event with the earliest deadline.
Sweep plus a Fenwick tree turns range counts over active values into O(log n) queries.
Sweep plus a segment tree maintains the covered length for union-area problems.
Offline queries sorted by right endpoint let a Fenwick tree count distinct values per range.