PK

PKBytes

Explore tracks
Chapter 22: Intervals, Events and Sweep-Line Algorithms
22.04Intermediate5 topics17 min5 interactive animations

One-dimensional sweep line

Sweeping a line over one dimension: sorting coordinates, maintaining the active set, the union of line segments, covered length and the earliest conflict.

Learning goals

  • Sweep over sorted endpoints and maintain a structure for the active intervals
  • Compute the total length covered by a union of segments
  • Compute the length covered at least k times
  • Detect the earliest conflict in a booking system, offline and online

Prerequisites

Difference array and event sweep

The sweep line is the general method: stop only where something changes, and keep just enough about the active objects to answer the question at hand.

22.04.1

Coordinate sorting

A one-dimensional sweep starts by turning the objects into a sorted list of **coordinates**, each tagged with what happens there (a segment starts, a segment ends) and which object it belongs to. Everything else is a loop over that list. Sorting dominates the cost: O(n log n) for n segments.

Sort the pairs of coordinate and event type, and decide the tie rule once. The union animation sorts the segments by start and marches across them: each segment either extends the current covered run or ends it and starts a new one.

Java
1// each endpoint is {coordinate, type, id}; type 0 = end, 1 = start, so ends sort first at equal coordinates
2static int[][] endpoints(int[][] segments) {
3    int[][] e = new int[segments.length * 2][];
4    for (int i = 0; i < segments.length; i++) {
5        e[2 * i] = new int[]{segments[i][0], 1, i};
6        e[2 * i + 1] = new int[]{segments[i][1], 0, i};
7    }
8    Arrays.sort(e, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
9    return e;
10}

Total length covered by a set of segments

Interactive · edit the input

Your input

Try
run reaches 4

sorted by start

[1, 4]
[3, 6]
[8, 10]
[9, 12]
[14, 15]

covered runs

[1, 4]
0123456789101112131415
Setup

Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.

Step 1 / 8
Java
1static int coveredLength(int[][] seg) {
2    Arrays.sort(seg, Comparator.comparingInt(a -> a[0]));        // sweep from left to right
3    int total = 0, curStart = seg[0][0], curEnd = seg[0][1];
4    for (int i = 1; i < seg.length; i++) {
5        if (seg[i][0] <= curEnd) curEnd = Math.max(curEnd, seg[i][1]);      // overlaps the open run: extend it
6        else { total += curEnd - curStart; curStart = seg[i][0]; curEnd = seg[i][1]; }   // a gap: close the run
7    }
8    return total + (curEnd - curStart);
9}

Live state

start

1

end

4

total

0

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L3start=1 end=4 total=0Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.
2L5segment=[3, 6] run=[1, 4] total=0[3, 6] starts inside the run: extend it to 6.
3L5segment=[8, 10] run=[1, 6] total=0[8, 10] starts after the run ends at 6: there is a gap.
4L6total=5Close the run [1, 6]: add its length 5. Total covered 5.
5L5segment=[9, 12] run=[8, 10] total=5[9, 12] starts inside the run: extend it to 12.
6L5segment=[14, 15] run=[8, 12] total=5[14, 15] starts after the run ends at 12: there is a gap.
7L6total=9Close the run [8, 12]: add its length 4. Total covered 9.
8L8return=10Total covered length 10. The uncovered gaps are exactly the spaces between runs.
22.04.2

Maintain active set

While sweeping, keep a structure holding the objects that currently cross the line. What the structure is depends on the question. A counter is enough for 'how many'. A **min-heap of end times** answers 'when does the next one finish'. A **sorted map** answers 'which active object is just before or after this one', which is how conflicts are found when bookings arrive online, one at a time.

An online calendar stores each booking's start and end in a TreeMap keyed by start. A new booking [s, e) conflicts only with the booking that starts at or before s (if it ends after s) or the booking that starts after s (if it starts before e). Looking at those two neighbours is O(log n); no other booking can conflict, because the stored bookings are disjoint.

Java
1// bookings are half-open [start, end); returns false (and does not store) on a conflict
2static boolean book(TreeMap<Integer, Integer> calendar, int start, int end) {
3    Map.Entry<Integer, Integer> before = calendar.floorEntry(start);      // starts at or before 'start'
4    if (before != null && before.getValue() > start) return false;
5    Map.Entry<Integer, Integer> after = calendar.ceilingEntry(start);     // starts at or after 'start'
6    if (after != null && after.getKey() < end) return false;
7    calendar.put(start, end);
8    return true;
9}

Start/end events: active count and maximum concurrency

Interactive · edit the input

Your input

Try

intervals

[0, 30]
[5, 10]
[15, 20]
[10, 15]
0123456789101112131415161718192021222324252627282930

events in sweep order

+0
+5
−10
+10
−15
+15
−20
−30

active count after each event

none
Setup

Turn every interval into two events, +1 at its start and −1 at its end, sort them, and sweep once keeping a running count. At equal coordinates ends come first, because [s, e) does not contain e: back-to-back intervals do not overlap.

Step 1 / 10
Java
1static int maxConcurrent(int[][] iv, boolean closed) {
2    List<int[]> events = new ArrayList<>();                          // {coordinate, +1 start / -1 end}
3    for (int[] x : iv) { events.add(new int[]{x[0], +1}); events.add(new int[]{x[1], -1}); }
4    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
5                       : closed ? Integer.compare(b[1], a[1]) : Integer.compare(a[1], b[1]));   // tie: closed -> start first; half-open -> end first
6    int active = 0, best = 0;
7    for (int[] e : events) {
8        active += e[1];                                              // a start opens one, an end closes one
9        best = Math.max(best, active);
10    }
11    return best;
12}

Live state

intervals

4

events

8

No condition evaluated on this step
Execution trace (dry run table)Show 10 steps
StepLineStateWhat happens
1L2intervals=4 events=8Turn every interval into two events, +1 at its start and −1 at its end, sort them, and sweep once keeping a running count. At equal coordinates ends come first, because [s, e) does not contain e: back-to-back intervals do not overlap.
2L8x=0 event=start active=1 best=1At 0: an interval starts, so 1 is active. New maximum: 1.
3L8x=5 event=start active=2 best=2At 5: an interval starts, so 2 are active. New maximum: 2.
4L8x=10 event=end active=1 best=2At 10: an interval ends, so 1 is active.
5L8x=10 event=start active=2 best=2At 10: an interval starts, so 2 are active.
6L8x=15 event=end active=1 best=2At 15: an interval ends, so 1 is active.
7L8x=15 event=start active=2 best=2At 15: an interval starts, so 2 are active.
8L8x=20 event=end active=1 best=2At 20: an interval ends, so 1 is active.
9L8x=30 event=end active=0 best=2At 30: an interval ends, so 0 are active.
10L11return=2Maximum concurrency 2: that many rooms (or platforms, or CPUs) are needed. Cost O(n log n) for the sort, O(n) for the sweep.
22.04.3

Line segment unions

The **union** of segments is the set of points covered by at least one of them. Sort by start and sweep, keeping the current covered run [runStart, runEnd]: if the next segment starts after runEnd, the run is finished (add its length) and a new run begins; otherwise extend runEnd. The gaps are exactly the spaces between runs.

The “Overlaps and gaps” preset covers [1, 6], [8, 12] and [14, 15] for a total of 5 + 4 + 1 = 10. “Nested” covers 10 even though three segments are given, and “Touching” (1-3 and 3-6) joins into one run of length 5.

Java
1static int unionLength(int[][] segments) {
2    int[][] a = segments.clone();
3    Arrays.sort(a, Comparator.comparingInt(x -> x[0]));
4    int total = 0;
5    int runStart = a[0][0], runEnd = a[0][1];
6    for (int i = 1; i < a.length; i++) {
7        if (a[i][0] > runEnd) {                              // gap: close the run
8            total += runEnd - runStart;
9            runStart = a[i][0];
10            runEnd = a[i][1];
11        } else {
12            runEnd = Math.max(runEnd, a[i][1]);
13        }
14    }
15    return total + (runEnd - runStart);
16}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(1) beyond the sorted copy

Total length covered by a set of segments

Interactive · edit the input

Your input

Try
run reaches 4

sorted by start

[1, 4]
[3, 6]
[8, 10]
[9, 12]
[14, 15]

covered runs

[1, 4]
0123456789101112131415
Setup

Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.

Step 1 / 8
Java
1static int coveredLength(int[][] seg) {
2    Arrays.sort(seg, Comparator.comparingInt(a -> a[0]));        // sweep from left to right
3    int total = 0, curStart = seg[0][0], curEnd = seg[0][1];
4    for (int i = 1; i < seg.length; i++) {
5        if (seg[i][0] <= curEnd) curEnd = Math.max(curEnd, seg[i][1]);      // overlaps the open run: extend it
6        else { total += curEnd - curStart; curStart = seg[i][0]; curEnd = seg[i][1]; }   // a gap: close the run
7    }
8    return total + (curEnd - curStart);
9}

Live state

start

1

end

4

total

0

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L3start=1 end=4 total=0Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.
2L5segment=[3, 6] run=[1, 4] total=0[3, 6] starts inside the run: extend it to 6.
3L5segment=[8, 10] run=[1, 6] total=0[8, 10] starts after the run ends at 6: there is a gap.
4L6total=5Close the run [1, 6]: add its length 5. Total covered 5.
5L5segment=[9, 12] run=[8, 10] total=5[9, 12] starts inside the run: extend it to 12.
6L5segment=[14, 15] run=[8, 12] total=5[14, 15] starts after the run ends at 12: there is a gap.
7L6total=9Close the run [8, 12]: add its length 4. Total covered 9.
8L8return=10Total covered length 10. The uncovered gaps are exactly the spaces between runs.
22.04.4

Coverage length

The union counts points covered **at least once**. Sometimes you need the length covered at least k times, or exactly k times. The event sweep gives it directly: between two consecutive event coordinates the active count is constant, so add the gap length to the total whenever the count at that stretch is at least k.

With k = 1 it reproduces the union length. With k = 2 it gives the length where segments overlap each other, which is useful for conflict reports.

Java
1// length covered by at least k of the half-open segments; segments must have start < end
2static long lengthCoveredAtLeast(int[][] segments, int k) {
3    TreeMap<Integer, Integer> delta = new TreeMap<>();
4    for (int[] s : segments) { delta.merge(s[0], +1, Integer::sum); delta.merge(s[1], -1, Integer::sum); }
5    long total = 0;
6    int active = 0;
7    Integer prev = null;
8    for (Map.Entry<Integer, Integer> e : delta.entrySet()) {
9        if (prev != null && active >= k) total += e.getKey() - prev;   // the stretch (prev, key) has constant count
10        active += e.getValue();
11        prev = e.getKey();
12    }
13    return total;
14}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n)

Total length covered by a set of segments

Interactive · edit the input

Your input

Try
run reaches 4

sorted by start

[1, 4]
[3, 6]
[8, 10]
[9, 12]
[14, 15]

covered runs

[1, 4]
0123456789101112131415
Setup

Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.

Step 1 / 8
Java
1static int coveredLength(int[][] seg) {
2    Arrays.sort(seg, Comparator.comparingInt(a -> a[0]));        // sweep from left to right
3    int total = 0, curStart = seg[0][0], curEnd = seg[0][1];
4    for (int i = 1; i < seg.length; i++) {
5        if (seg[i][0] <= curEnd) curEnd = Math.max(curEnd, seg[i][1]);      // overlaps the open run: extend it
6        else { total += curEnd - curStart; curStart = seg[i][0]; curEnd = seg[i][1]; }   // a gap: close the run
7    }
8    return total + (curEnd - curStart);
9}

Live state

start

1

end

4

total

0

No condition evaluated on this step
Execution trace (dry run table)Show 8 steps
StepLineStateWhat happens
1L3start=1 end=4 total=0Sort by start and sweep, keeping the current run [start, end]. A segment that starts inside the run extends it; a segment that starts after the run ends closes it and begins a new one.
2L5segment=[3, 6] run=[1, 4] total=0[3, 6] starts inside the run: extend it to 6.
3L5segment=[8, 10] run=[1, 6] total=0[8, 10] starts after the run ends at 6: there is a gap.
4L6total=5Close the run [1, 6]: add its length 5. Total covered 5.
5L5segment=[9, 12] run=[8, 10] total=5[9, 12] starts inside the run: extend it to 12.
6L5segment=[14, 15] run=[8, 12] total=5[14, 15] starts after the run ends at 12: there is a gap.
7L6total=9Close the run [8, 12]: add its length 4. Total covered 9.
8L8return=10Total covered length 10. The uncovered gaps are exactly the spaces between runs.
22.04.5

Earliest conflict

Given a list of bookings, find the first moment at which two of them conflict. Sort the bookings by start and keep the largest end seen so far; the first booking that starts **before** that end is in conflict, and the conflict begins at its start. The sweep can stop immediately, which is what the animation reports.

The “Conflict at 11” preset (bookings 9-10, 14-16, 10-12, 11-13) finds that B4 starts at 11 while B3 (10-12) is still active. “No conflict” shows back-to-back bookings, and “Two start together” shows that equal starts conflict at once, at time 5.

Java
1// bookings are half-open {start, end}; returns {time, indexOfLaterBooking, indexOfEarlierBooking} or null
2static int[] earliestConflict(int[][] bookings) {
3    Integer[] order = new Integer[bookings.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, Comparator.comparingInt(i -> bookings[i][0]));
6    int holder = -1;                                         // booking with the largest end so far
7    for (int i : order) {
8        if (holder >= 0 && bookings[i][0] < bookings[holder][1]) return new int[]{bookings[i][0], i, holder};
9        if (holder < 0 || bookings[i][1] > bookings[holder][1]) holder = i;
10    }
11    return null;
12}

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

Space

O(n) for the index array

Earliest scheduling conflict by sweeping

Interactive · edit the input

Your input

Try

bookings by start

B1
B3
B4
B2
012345678910111213141516
Setup

Sort by start time and sweep. Remember the booking with the largest end so far. The next booking conflicts exactly when it starts before that end, because everything earlier ended no later.

Step 1 / 5
Java
1static int[] firstConflict(int[][] bookings) {          // returns {start of the conflict, index of the earlier booking}
2    Integer[] idx = new Integer[bookings.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
3    Arrays.sort(idx, Comparator.comparingInt(i -> bookings[i][0]));
4    int latest = -1, latestEnd = Integer.MIN_VALUE;           // booking with the largest end so far
5    for (int i : idx) {
6        if (latest >= 0 && bookings[i][0] < latestEnd) return new int[]{bookings[i][0], latest};   // starts before something ends
7        if (bookings[i][1] > latestEnd) { latest = i; latestEnd = bookings[i][1]; }
8    }
9    return null;                                            // no two bookings overlap
10}

Live state

bookings

4

No condition evaluated on this step
Execution trace (dry run table)Show 5 steps
StepLineStateWhat happens
1L3bookings=4Sort by start time and sweep. Remember the booking with the largest end so far. The next booking conflicts exactly when it starts before that end, because everything earlier ended no later.
2L6booking=B1 start=9 latest end=noneB1 is the first booking.
3L6booking=B3 start=10 latest end=10B3 starts at 10, at or after 10: no conflict so far.
4L6booking=B4 start=11 latest end=12B4 starts at 11, before B3 ends at 12: this is the earliest conflict.
5L6return=11 (with B3)Conflict starting at time 11 between B4 and B3. Stop: the sweep finds it as soon as it happens.

Practice ladder

Now try it yourself

Easy

  • Meeting Rooms
  • My Calendar I

Medium

  • My Calendar II
  • Merge Intervals
  • Divide Intervals Into Minimum Number of Groups

Advanced

  • My Calendar III
  • Rectangle Area II

Key takeaways

  • A sweep sorts coordinates once and then processes only the places where something changes.
  • The structure for the active set is chosen by the question: a counter, a heap of ends or a sorted map.
  • The union length adds the length of each run of overlapping segments.
  • Covered-at-least-k length adds each gap between events whose active count is at least k.
  • The earliest conflict is the first booking, in start order, that starts before the largest end so far.