Activity Selection, in depth: earliest finish first, two proofs, failing orderings, endpoint rules, weighted DP and k rooms

The problem, stated precisely

The input is n activities, each a pair (s, f) with s < f. We treat each activity as the half-open interval [s, f): it occupies the resource from s up to, but not including, f. So an activity ending at 11:00 and another starting at 11:00 are compatible. Two activities are compatible when one finishes no later than the other starts. The goal is a largest set of pairwise compatible activities. Note that we maximise the count, not total time used and not total value; those are different problems, and two of them are covered later.

In graph terms, build a vertex per activity and an edge between every overlapping pair. That is an interval graph, and we want a maximum independent set in it. For general graphs that problem is NP-hard. For interval graphs, the left-to-right structure of time makes it solvable in O(n log n) time.

The algorithm

The algorithm sorts by finish time and makes one pass, remembering only the finish time of the last kept activity:

def select_activities(acts):
    """acts: list of (name, start, finish), half-open [start, finish).
    Returns a maximum-size list of pairwise compatible activities."""
    chosen, last_finish = [], float("-inf")
    for name, s, f in sorted(acts, key=lambda a: (a[2], a[1])):  # finish, then start
        if s >= last_finish:          # compatible with everything kept so far
            chosen.append(name)
            last_finish = f
    return chosen

The sort costs O(n log n) and the pass costs O(n). If the input already arrives sorted by finish time, as with a stream of bookings ordered by end time, the whole thing is O(n) time and O(1) extra memory apart from the output. Comparing against only the last kept activity is enough, because every kept activity finishes at or before it.

The secondary sort key does not affect the count. Among activities with the same finish time, at most one can be kept, so the tie-breaker only decides which one. Making it explicit keeps the output deterministic, which matters when results are compared across runs or shown to users.

Worked example: ten lab bookings

Ten lab bookings for one day, in hours on a 24-hour clock: A [9,11), B [10,12), C [11,13), D [9,14), E [12,15), F [13,14), G [14,16), H [15,17), I [16,18) and J [17,19). Sorted by finish time, ties broken by start, the order is A, B, C, D, F, E, G, H, I, J. Note that F (finish 14) comes before E (finish 15), even though E starts first.

The result is A, C, F, G, I: five bookings. A brute-force search over every subset of the ten bookings confirms that no compatible set of six exists. It also finds three optimal sets of five: A, C, F, G, I; A, C, F, G, J; and A, C, F, H, J. Greedy returns the one whose last booking finishes earliest, at 18:00, which leaves the most room for anything added later.

Why earliest finish is optimal

There are two standard proofs. Both are worth knowing, because the same patterns prove most greedy algorithms.

Greedy stays ahead. Let the greedy picks, in order, be g1, g2, ..., gk, and let any optimal solution, sorted by time, be o1, o2, ..., om. Claim: for every i up to k, f(gi) <= f(oi). For i = 1 this is true because g1 has the smallest finish time of all activities. Suppose it holds for i - 1. Then oi starts at or after f(o(i-1)), which is at or after f(g(i-1)). So oi was still available when greedy made its i-th choice, and greedy chose the available activity with the earliest finish, so f(gi) <= f(oi). Now suppose m > k. Then o(k+1) starts after f(ok) >= f(gk), so it was still available after greedy's last pick, and greedy would have taken it. That contradicts greedy stopping at k, so m = k.

Exchange argument. Take any optimal solution O and let a be the activity with the earliest finish overall. If a is not in O, remove O's first activity, which finishes no earlier than a, and put a in its place. Nothing else conflicts with a, because everything else in O starts after that first activity ended, which is at or after f(a). The new set has the same size, so it is also optimal. So some optimal solution starts with greedy's first choice. Remove a and every activity that overlaps it, and what is left is the same problem on a smaller input, with the same structure. By induction, greedy is optimal. This is the pattern the site's article on job scheduling with deadlines uses as well.

Orderings that look right and fail

Three other rules sound just as reasonable. Each one fails, and the smallest counterexamples are worth remembering:

The first two fail for clear reasons. An early start says nothing about how long an activity blocks the room. A short activity can sit across the boundary between two longer ones and knock out both. The third rule is more tempting, because it seems to look ahead. The counterexample is P [0,3), Q [3,6), R [6,9), S [9,12) along the top, three copies of [2,4) under the P/Q boundary, three copies of [8,10) under the R/S boundary, and one M [5,7) across the Q/R boundary. M has only 2 conflicts, the fewest of any interval, so the rule takes it, which removes Q and R. From what remains, the rule can take at most two more, for 3 in total. Greedy by finish time takes P, Q, R, S, which is 4. If a proposed greedy rule has no stays-ahead or exchange proof, assume it is wrong until you have tested it against brute force on random small inputs.

Endpoints, ties and real timestamps

The code above uses s >= last_finish, which treats intervals as half-open. If you write s > last_finish instead, an activity ending at 11 blocks one starting at 11, which is the closed-interval reading. On the lab bookings, that one-character change gives A, F, H: three bookings instead of five, because C, G and I each start exactly when the previous kept booking ends. Neither version is a bug in itself. The bug is when the code and the business rule disagree. Calendar systems almost always mean half-open: a 10:00 to 11:00 meeting and an 11:00 to 12:00 meeting do not clash. If changeover time is needed, such as cleaning a lab, add it to each finish time explicitly instead of switching to a strict comparison.

Real timestamps add their own traps. Convert every time to UTC epoch values before comparing, so that daylight-saving changes do not create overlaps or gaps. Reject records where s >= f before sorting, because an activity with negative duration will quietly break the stays-ahead argument. And be careful with floating-point hours: 0.1 + 0.2 is not exactly 0.3, so store integer minutes or seconds.

When activities have values: weighted DP

Now give each activity a value, such as revenue, and maximise the total value instead of the count. Greedy by finish time no longer works. Take A [0,3) worth 2, B [2,6) worth 9, C [4,7) worth 3, D [6,9) worth 4 and E [8,11) worth 5. Greedy picks A, C, E for a value of 10, but B with E is worth 14. No ordering rule fixes this. The standard solution is dynamic programming over activities sorted by finish time. For activity j, let p(j) be the number of earlier activities that finish at or before j starts, found with binary search. Then best[j] = max(best[j-1], best[p(j)] + w_j).

import bisect

def max_weight(acts):                       # acts: (name, start, finish, weight)
    acts = sorted(acts, key=lambda a: a[2])
    ends = [a[2] for a in acts]
    best = [0] * (len(acts) + 1)
    for j, (_, s, f, w) in enumerate(acts, 1):
        p = bisect.bisect_right(ends, s, 0, j - 1)   # activities compatible with j
        best[j] = max(best[j - 1], best[p] + w)
    return best[-1]

This runs in O(n log n) and needs O(n) memory. Tracing back through the table recovers B and E. When all weights are equal, the DP and greedy give the same count, and greedy is the simpler and faster choice.

More than one room

With k identical rooms, the question becomes: which activities should you accept so that the largest number fit into k rooms? Greedy still works, with a best-fit rule. Process activities by finish time. For each one, find the room that became free most recently but no later than the activity's start, and put the activity there. If no room is free, reject it. Choosing the latest free room keeps rooms that free up earlier available for activities that start earlier.

import bisect

def max_in_k_rooms(acts, k):
    free_at = [float("-inf")] * k            # sorted finish time of each room
    kept = []
    for name, s, f in sorted(acts, key=lambda a: (a[2], a[1])):
        i = bisect.bisect_right(free_at, s) - 1   # latest room free by time s
        if i >= 0:
            free_at.pop(i)
            bisect.insort(free_at, f)
            kept.append(name)
    return kept

With k = 2 on the lab bookings, this keeps 9 of the 10, rejecting only D [9,14), and an exhaustive search over all assignments confirms that 9 is the maximum. The list operations make this O(nk); with a balanced tree or a sorted container it becomes O(n log k). This is a different question from the one in the meeting-rooms article, which asks how many rooms are needed to run every activity. That answer is the maximum number of activities that overlap at any one time, and for the lab bookings it is 3.

Failure modes and trade-offs

The general lesson is the trade-off behind every greedy method: it is fast and simple because it never revisits a decision, and that is only safe when a proof says no later information could change the decision. Change the objective, add weights or add precedence constraints, and you need a new proof or a different algorithm.

What to do next

1. Implement select_activities and test it against a brute-force search on a few thousand random inputs of up to 12 activities.
2. Write down your domain's endpoint rule (half-open or closed) and add a test with back-to-back activities that pins it.
3. Write out the stays-ahead proof yourself for the lab example, checking f(gi) <= f(oi) at each step.
4. Build the 11-interval fewest-conflicts counterexample and confirm it returns 3 against greedy's 4.
5. If your activities have values, switch to the weighted DP and compare its total with greedy's on your real data.
6. For several resources, implement the best-fit k-room version and compare its accepted count with the room count from the meeting-rooms algorithm.
7. Read about Huffman coding to see an exchange argument with a heap, and the interval tree for the case where bookings arrive one at a time and must be checked against what is already accepted.