Sweep Line | Algorithms & Data Structures

Algorithm Summary

Sweep-line algorithms are especially useful for interval problems. Sort the intervals or their endpoints, then scan from left to right while maintaining only the state needed at the current position.

Common Java sorting forms:

Java

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
Arrays.sort(intervals, (a, b) ->
    a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

Collections.sort(list, (a, b) ->
    a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

intervalsList.sort((a, b) -> Integer.compare(a.get(0), b.get(0)));

When a problem asks how many intervals are active at the same moment, split each interval into a start event with weight +1 and an end event with weight -1.

Java

for (int[] interval : intervals) {
    events.add(new int[]{interval[0], 1});
    events.add(new int[]{interval[1], -1});
}

Examples

Meeting Rooms — LC 252

Sort by start time. If an interval ends after the next interval begins, the meetings overlap.

Java

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i + 1 < intervals.length; i++) {
    if (intervals[i][1] > intervals[i + 1][0]) return false;
}
return true;

Meeting Rooms II — LC 253

Convert starts and ends into weighted events. Sort by time and process end events before start events at the same time. The maximum running total is the number of rooms required.

Java

events.sort((a, b) -> a[0] == b[0]
    ? Integer.compare(a[1], b[1])
    : Integer.compare(a[0], b[0]));

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

Merge Intervals — LC 56

Sort intervals and carry a current merged interval. Extend it while the next interval overlaps; otherwise, save it and start a new range.

Insert Interval — LC 57

Add intervals that finish before the new interval, merge every overlapping interval into the new interval, then append the remaining intervals.

Remove Interval — LC 1272

For each interval, keep it unchanged when it does not overlap the removed range. For an overlap, preserve the valid left fragment, right fragment, or both.

Java

for (int[] interval : intervals) {
    if (interval[1] <= removed[0] || interval[0] >= removed[1]) {
        result.add(List.of(interval[0], interval[1]));
    } else {
        if (interval[0] < removed[0]) result.add(List.of(interval[0], removed[0]));
        if (interval[1] > removed[1]) result.add(List.of(removed[1], interval[1]));
    }
}

The Skyline Problem — LC 218

Represent a building's left edge as an add-height event and its right edge as a remove-height event. A max-heap tracks the active heights. Whenever the maximum changes, record a new key point.