Lesson 15.4 · Intervals

Sweep Line: Counting What's Active

Turn each interval into a +1 event at its start and a −1 at its end, sort events, and the running sum is how many are active.

12 min

Think of it like this

A doorman with a clicker at a party: click up when someone enters, down when someone leaves. The highest reading during the night is the most people inside at once.

1.Events instead of intervals

For "how many rooms are needed", the answer is the maximum number of meetings in progress at the same time. Sort all start times and all end times separately; walk them like a merge, adding 1 for a start and subtracting 1 for an end. Process an end before a start at the same time if a meeting ending at 10:00 frees the room for one starting at 10:00.

Rooms.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] meetings = {{0, 30}, {5, 10}, {15, 20}};
        int n = meetings.length;
        int[] starts = new int[n], ends = new int[n];
        for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, best = 0, e = 0;
        for (int s : starts) {
            while (ends[e] <= s) { rooms--; e++; }   // meetings that ended free a room
            rooms++;
            best = Math.max(best, rooms);
        }
        System.out.println("rooms needed: " + best);
    }
}

Output

rooms needed: 2

Remember

+1 at start, −1 at end; the running sum is the active count.
Decide the order of events at equal times.
Also solvable with a min-heap of end times.

Common mistakes

Processing a start before an end at the same time when touching shouldn't overlap.

Command Palette

Sweep Line: Counting What's Active

1.Events instead of intervals