Difference-array event sweep

Replace every interval [s, e) by two **events**: at time s the active count goes up by 1, at time e it goes down by 1. Sort all events by time and process them in order; between events nothing changes, so only event times matter, whatever the distance between them.

The “Meeting rooms” preset of the animation turns four meetings into eight events, shows the active count after each, and tracks the maximum. This is why the technique is called a **sweep line**: an imaginary vertical line moves across the time axis and stops only at events.

1// events: {time, delta}; delta = +1 for a start, -1 for an end
2static int[][] toEvents(int[][] intervals) {
3    int[][] events = new int[intervals.length * 2][];
4    int k = 0;
5    for (int[] iv : intervals) {
6        events[k++] = new int[]{iv[0], +1};
7        events[k++] = new int[]{iv[1], -1};
8    }
9    return events;
10}

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}

When a start and an end share the same time, the processing order decides the answer. For half-open intervals [s, e) a meeting that ends at 3 has left before one that starts at 3 arrives, so **ends are processed first** at equal times. For closed intervals the two meetings share the instant 3, so **starts come first**.

The animation shows both: with the data 1-3, 3-5, 5-7, the “Back-to-back: half-open needs 1” preset reports maximum concurrency 1, and “Back-to-back: closed needs 2” reports 2. A single comparator decides it: sort by time, then by delta with -1 before +1 for half-open.

1// half-open: at equal times the end (-1) sorts before the start (+1)
2static void sortEvents(int[][] events) {
3    Arrays.sort(events, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(x[1], y[1]));
4}
5// for closed intervals reverse the tie-break: Integer.compare(y[1], x[1])

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}

The **active count** after processing an event is the running sum of the deltas, which is the number of intervals containing the current time. A difference array gives the same sweep for small integer coordinates without sorting: add 1 at the start index, subtract 1 at the end index, and a prefix sum over the array gives the count at every position.

For half-open intervals [s, e) the two array writes are diff[s]++ and diff[e]--. Positions are bounded by the largest coordinate, so this suits days of a year or minutes of a day; for huge coordinates sort events or compress them, as the last group in this chapter shows.

1// counts[t] = number of half-open intervals [s, e) containing time t, for 0 <= t < maxTime
2static int[] activeCounts(int[][] intervals, int maxTime) {
3    int[] diff = new int[maxTime + 1];
4    for (int[] iv : intervals) { diff[iv[0]]++; diff[iv[1]]--; }
5    int[] counts = new int[maxTime];
6    int running = 0;
7    for (int t = 0; t < maxTime; t++) { running += diff[t]; counts[t] = running; }
8    return counts;
9}

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}

**Maximum concurrency** is the largest active count over the sweep, and it answers 'how many rooms, platforms, servers or CPUs are needed'. A TreeMap from time to net delta handles repeated times and arbitrary coordinates, and iterating it in key order is the sweep. Because all events at one time are combined into a single net delta, ties cannot be mis-ordered: an end and a start at the same time cancel before the count is compared to the maximum.

On the “All at once” preset, 4 nested intervals all active together give concurrency 4, and on the classic meeting-rooms data the answer is 3. The cost is O(n log n) for the map operations.

1static int maxConcurrency(int[][] intervals) {                // half-open [start, end)
2    TreeMap<Integer, Integer> delta = new TreeMap<>();
3    for (int[] iv : intervals) {
4        delta.merge(iv[0], +1, Integer::sum);
5        delta.merge(iv[1], -1, Integer::sum);
6    }
7    int active = 0, best = 0;
8    for (int d : delta.values()) {                           // keys in increasing time order
9        active += d;
10        best = Math.max(best, active);
11    }
12    return best;
13}

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}

The difference array also solves **many range updates, one read**: 'add v to every element from l to r' repeated m times and then read the whole array. Record diff[l] += v and diff[r + 1] -= v for each update, then take one prefix sum. Each update is O(1), and the final pass is O(n), so m updates cost O(m + n) instead of O(m · n).

For example, on an array of 5 zeros, adding 2 to indexes 1 to 3 and 3 to indexes 2 to 4 sets diff to [0, 2, 3, 0, -2, -3], whose prefix sums are [0, 2, 5, 5, 3, 0], so the first five entries are 0, 2, 5, 5, 3.

A difference array supports updates in bulk but not reads between updates. If you must interleave range updates and queries, use a Fenwick or segment tree, introduced later in the course.

1// updates[i] = {l, r, v}: add v to every index in [l, r] (inclusive)
2static int[] applyRangeUpdates(int n, int[][] updates) {
3    int[] diff = new int[n + 1];
4    for (int[] u : updates) {
5        diff[u[0]] += u[2];
6        diff[u[1] + 1] -= u[2];
7    }
8    int[] result = new int[n];
9    int running = 0;
10    for (int i = 0; i < n; i++) { running += diff[i]; result[i] = running; }
11    return result;
12}