Activity Selection Greedy

Description

You have one room and many meeting requests with start and end times, and you want to hold as many meetings as possible. Checking every subset is exponential. The obvious greedy orders, earliest start or shortest meeting first, both fail. Sorting by end time and taking every meeting that still fits is provably right. The same sort also finds the fewest points that hit every interval, and the fewest intervals to remove so the rest don't overlap.

We'll go from simple to more technical:

1. The pattern: sort by end, keep every meeting that starts after the last kept one ends.
2. A second flavor: the fewest arrows (points) that hit every interval.
3. Where interval scheduling shows up (rooms, CPUs, ad slots, maintenance windows).
4. What breaks it: the wrong sort key, the boundary rule, comparator overflow, weights.

The approach

int maxMeetings(int[] start, int[] end) {
    Integer[] order = new Integer[start.length];
    for (int i = 0; i < order.length; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(end[a], end[b]));   // earliest end first
    int count = 0;
    long lastEnd = Long.MIN_VALUE;
    for (int i : order) {
        if (start[i] > lastEnd) {          // strictly after: touching meetings conflict in this problem
            count++;
            lastEnd = end[i];
        }
    }
    return count;
}

def max_meetings(start: list[int], end: list[int]) -> int:
    count = 0
    last_end = float("-inf")
    for e, s in sorted(zip(end, start)):         # earliest end first
        if s > last_end:                         # strictly after: touching meetings conflict in this problem
            count += 1
            last_end = e
    return count

Taking the meeting that ends first leaves the room free as early as possible for everything else. Exchange argument: any optimal schedule's first meeting ends no earlier than the earliest-ending one, so swapping it for the earliest-ending one keeps the schedule valid and the same size.

The other orders have counterexamples. Earliest start takes [1, 10] from {[1, 10], [2, 3], [4, 5]} and holds 1 meeting instead of 2. Shortest first takes [4, 7] from {[1, 5], [4, 7], [6, 10]} and blocks both others. Whether a meeting may start exactly when another ends is a rule of the problem, not the algorithm: here it may not (>), so [1, 2], [2, 3], [3, 4] allows 2 meetings; with back-to-back allowed (>=) it would be 3.

A second flavor: the fewest points that hit every interval

Balloons span [start, end] on a line, and an arrow shot at x bursts every balloon with start <= x <= end. The fewest arrows uses the same sort:

int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));   // never a[1] - b[1]: it can overflow
    int arrows = 1;
    int pos = points[0][1];                // shoot at the earliest end
    for (int[] p : points) {
        if (p[0] > pos) {                  // starts after the arrow: needs a new one
            arrows++;
            pos = p[1];
        }
    }
    return arrows;
}

def find_min_arrow_shots(points: list[list[int]]) -> int:
    points = sorted(points, key=lambda p: p[1])  # a key function: nothing to overflow
    arrows = 1
    pos = points[0][1]                           # shoot at the earliest end
    for start, end in points:
        if start > pos:                          # starts after the arrow: needs a new one
            arrows += 1
            pos = end
    return arrows

Shooting at the earliest end bursts every balloon that has already started, as late as possible. Balloons that merely touch the arrow's position are burst (closed intervals, so > starts a new arrow). With coordinates near ±2^31, the comparator a[1] - b[1] overflows: -2147483647 - 2147483647 wraps to 2, sorting the wrong balloon first. Integer.compare doesn't overflow. In Python you sort with a key function - sorted(points, key=lambda p: p[1]) - so there's no comparator to get wrong.

The minimum number of intervals to remove so the rest don't overlap is n minus the maximum number you can keep - the same greedy again.

Where you'll see it

Booking a single shared resource - a meeting room, a test device, one build agent - to serve the most requests; picking the maximum set of non-conflicting calendar events; and placing the fewest monitoring checkpoints that cover every time window all use earliest-end greedy.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why sort by end time rather than start time?

2. [1, 2], [2, 3], [3, 4]: is the answer 2 or 3?

3. Why can (a, b) -> a[1] - b[1] sort intervals wrongly?

Key takeaways

• Most non-overlapping intervals: sort by end, take each one that starts after the last taken ends.
• Earliest start and shortest first both fail; prove the earliest end with an exchange argument.
• Touching intervals: > or >= is the problem's rule - read it.
• Fewest stabbing points (arrows) uses the same sort; fewest removals = n - maximum kept.
• Compare with Integer.compare, never by subtracting.