Activity Selection

The activity-selection problem is the textbook interval-scheduling problem: given n activities each with a start and finish time, choose the maximum-size subset of mutually non-overlapping activities. The optimal greedy is shockingly simple: sort by finish time, then walk left-to-right, taking each activity whose start time is ≥ the finish time of the last taken activity. It runs in O(n log n) (sort-dominated) and is one of the cleanest examples of a provably correct greedy in the curriculum — its exchange-argument correctness proof is a model for how to prove any greedy is optimal. The unweighted version is the greedy story; the weighted version (interval scheduling maximization with weights) is famously not greedy and requires dynamic programming.

1. Intuition — The Conference-Room Booker

Picture a single conference room and a stack of meeting requests, each marked with a start time and an end time. You’re the room admin; your goal is to fit the most meetings into the day’s calendar (you don’t care about meeting importance — just count). Some pairs of meetings overlap, so you can’t accept all of them.

A natural-but-wrong instinct is to grab whichever meeting starts earliest. That’s bad: an early-starting meeting might also end very late, blocking out a stretch of the day during which several short later meetings could have fit. (See §5 for the explicit counterexample.)

A second wrong instinct is to grab the shortest meeting first. Also bad: a short meeting in the middle of the day can disqualify two non-overlapping longer meetings on either side. (Counterexample: meetings A=[1,4], B=[3,5], C=[5,8]. Shortest is B, but picking B knocks out both A and C.)

The right instinct is to grab whichever meeting ends earliest. Pick that one, then look at the remaining meetings whose start is ≥ your last meeting’s end, and repeat. Why earliest-ending? Because it leaves the maximum amount of remaining day free for the rest of the schedule — the most room for the greedy choice to keep paying off. The exchange-argument proof in §5 makes this precise.

2. Tiny Worked Example

Six activities (start, finish):

A1: [1, 4]
A2: [3, 5]
A3: [0, 6]
A4: [5, 7]
A5: [3, 9]
A6: [8, 10]

Step 1: sort by finish time.

A1: [1, 4]
A2: [3, 5]
A3: [0, 6]
A4: [5, 7]
A5: [3, 9]
A6: [8, 10]

(Already in finish-time order — convenient for the example.)

Step 2: greedy walk.

Step	Activity	Last finish	Decision
1	A1 [1,4]	-∞	take. last_finish = 4.
2	A2 [3,5]	4	start 3 < 4 → conflict. skip.
3	A3 [0,6]	4	start 0 < 4 → conflict. skip.
4	A4 [5,7]	4	start 5 ≥ 4 → take. last_finish = 7.
5	A5 [3,9]	7	start 3 < 7 → conflict. skip.
6	A6 [8,10]	7	start 8 ≥ 7 → take. last_finish = 10.

Selected: A1, A4, A6 — three activities. No four-activity subset is non-overlapping (verifiable by exhaustion).

3. Pseudocode

activity_selection(intervals):                  # intervals: list of (start, finish)
    sort intervals by finish time ascending
    selected := empty list
    last_finish := -infinity
    for (start, finish) in intervals:
        if start >= last_finish:                 # use ≥ if intervals are half-open
            selected.append( (start, finish) )
            last_finish := finish
    return selected

The >= vs > choice matters and depends on the interval convention (see §10.3). For half-open intervals [start, finish), two intervals where one ends at t and another starts at t do not overlap, so >= is correct. For closed intervals [start, finish], they share a point, and you want > instead. Default to half-open in interview solutions; flag the convention explicitly.

4. Python Implementation

def activity_selection(intervals):
    """Return maximum-size set of mutually non-overlapping intervals.
 
    intervals: iterable of (start, finish) tuples (half-open: [start, finish)).
    Returns: list of selected (start, finish) tuples in finish-time order.
    """
    if not intervals:
        return []
 
    # Sort by finish time ascending. Stable sort means ties break by input order.
    sorted_iv = sorted(intervals, key=lambda iv: iv[1])
 
    selected = []
    last_finish = float('-inf')
    for start, finish in sorted_iv:
        if start >= last_finish:                # half-open intervals don't conflict at boundary
            selected.append((start, finish))
            last_finish = finish
 
    return selected
 
 
# Variant: just return the count (LC-style).
def max_non_overlapping(intervals):
    if not intervals:
        return 0
    sorted_iv = sorted(intervals, key=lambda iv: iv[1])
    count = 0
    last_finish = float('-inf')
    for start, finish in sorted_iv:
        if start >= last_finish:
            count += 1
            last_finish = finish
    return count

The whole algorithm is one sort plus one linear pass — twelve lines, all of them obvious in hindsight. The cleverness is which sort key to use; the rest is bookkeeping.

4.1 LC 435 — Non-overlapping Intervals (the dual problem)

LC 435 asks for the minimum number of intervals to remove to make the rest non-overlapping. By the duality removed = total - kept, the answer is n - max_non_overlapping(intervals), which the same greedy computes.

def erase_overlap_intervals(intervals):
    """LC 435. Min removals so remaining intervals are non-overlapping."""
    if not intervals:
        return 0
    intervals.sort(key=lambda iv: iv[1])
    kept = 0
    last_finish = float('-inf')
    for start, finish in intervals:
        if start >= last_finish:
            kept += 1
            last_finish = finish
    return len(intervals) - kept

4.2 LC 452 — Minimum Number of Arrows to Burst Balloons

A balloon at [xstart, xend] is burst by an arrow at any x ∈ [xstart, xend]. Minimum arrows = maximum chain of intervals such that each chain shares a common point — equivalently, min arrows is the count of “groups of mutually overlapping balloons.” This reduces to the same greedy: sort by xend, fire one arrow at the earliest-ending balloon’s xend, then skip over every balloon whose xstart ≤ xend. Repeat for the next un-burst balloon.

def find_min_arrow_shots(points):
    """LC 452. Minimum arrows to burst all balloons (closed intervals)."""
    if not points:
        return 0
    points.sort(key=lambda p: p[1])
    arrows = 1
    arrow_pos = points[0][1]
    for x_start, x_end in points[1:]:
        if x_start > arrow_pos:                 # this balloon needs a NEW arrow
            arrows += 1
            arrow_pos = x_end
    return arrows

The problem statement uses closed intervals (a point xend does burst a balloon [xend, xend+1]), so the comparison is > not >=. This is exactly the >=-vs-> subtlety from §3 in action — get the convention wrong and the answer is off by n - 1.

5. Why Earliest-Finish Works — Exchange-Argument Proof

Theorem. The “sort by finish time, take earliest-finishing compatible” greedy produces a maximum-size set of mutually non-overlapping intervals.

Setup. Let the intervals be sorted so f₁ ≤ f₂ ≤ … ≤ fₙ (finish times). Let G = (g₁, g₂, …, gₖ) be the greedy’s chosen indices (in order). Let O = (o₁, o₂, …, oₘ) be any optimal solution (also in finish-time order). We will prove k = m (so the greedy is optimal in cardinality).

Claim. For every i ∈ {1, 2, …, k}, the greedy’s i-th choice finishes no later than O’s i-th choice. Formally: f_{g_i} ≤ f_{o_i} for all i ≤ k.

Proof of claim, by induction on i.

Base case (i = 1). The greedy picks the interval with the smallest finish time of all intervals. So f_{g_1} ≤ f_{o_1} trivially — g₁ finishes no later than any interval, including o₁.

Inductive step. Suppose the claim holds for i - 1: f_{g_{i-1}} ≤ f_{o_{i-1}}.

Since O is non-overlapping, o_i starts at s_{o_i} ≥ f_{o_{i-1}} ≥ f_{g_{i-1}} (the second inequality is the inductive hypothesis). So at the moment the greedy chooses g_i, the interval o_i is available to the greedy — it doesn’t conflict with g_{i-1} (or anything earlier). The greedy chooses the earliest-finishing available interval, which finishes no later than o_i. Hence f_{g_i} ≤ f_{o_i}. ✓

Now finish the theorem. Suppose for contradiction that m > k, i.e., O has more intervals than the greedy. Then o_{k+1} exists. By the claim applied to i = k, f_{g_k} ≤ f_{o_k}. Since O is non-overlapping, s_{o_{k+1}} ≥ f_{o_k} ≥ f_{g_k} — so at the moment after the greedy picked g_k, the interval o_{k+1} was available. But the greedy terminated without picking anything more — contradicting the greedy’s rule of taking every available interval. So m ≤ k. Combined with k ≤ m (since O is optimal), we get k = m. ∎

Why this proof is the gold standard. This is the canonical exchange argument for greedy correctness — the same shape of proof works for Huffman Coding, Kruskal’s Algorithm, the fractional knapsack, and every other “provably correct” greedy. The structure is always:

1. Define greedy output G and an arbitrary optimum O.
2. Prove an invariant — typically that the greedy’s i-th choice “dominates” the optimum’s i-th choice along the relevant axis (here, finish time).
3. Conclude that the greedy is at least as long / heavy / cheap as the optimum.

Memorize this template — interviewers love asking “prove your greedy is correct” and the answer is almost always a structural rewording of this proof.

6. Why Other Sort Orders Fail (Counterexamples)

6.1 Sort by start time — fails

Consider [(0, 10), (1, 2), (3, 4), (5, 6)]. Sorting by start picks (0, 10) first; it conflicts with all three others, leaving only one selected. The optimum is 3: (1,2), (3,4), (5,6).

The lesson: a single early-starting long interval can block the whole rest of the schedule. Earliest-finish avoids this — long intervals have late finishes, so they sort to the back and the greedy considers (and takes) the short early ones first.

6.2 Sort by length (shortest first) — fails

Consider [(1, 5), (4, 6), (5, 9)]. Lengths are 4, 2, 4. Shortest is (4, 6); taking it conflicts with both others, leaving one selected. The optimum is 2: (1,5), (5,9).

The lesson: a short interval can be a “wedge” between two non-overlapping longer ones; taking the wedge knocks out two for one.

6.3 Sort by fewest conflicts — fails

The “interval with the fewest overlaps” heuristic seems clever but constructs counterexamples easily. A classic CLRS exercise (§16.1-3) gives an explicit configuration where the fewest-conflict heuristic loses by a factor of 4.

The collective moral: in greedy algorithms, the sort key matters more than the algorithm. Two greedies that differ only in their sort order can be wildly different in correctness.

7. Complexity

7.1 Time — O(n log n)

• Sort by finish time: O(n log n) — dominant.
• Linear scan with greedy choice: O(n).
• Total: O(n log n).

If the input is already sorted by finish time (e.g., events from a time-ordered log), the algorithm is O(n). This is sometimes the right way to frame it: “given an event stream sorted by finish time, this is a streaming O(1)-per-event algorithm.”

7.2 Space — O(1) extra

The selected list is at most O(n), but we typically count that as output, not working memory. The greedy itself tracks one variable (last_finish).

8. Variants

8.1 Weighted Interval Scheduling — DP, NOT greedy

If each interval has a weight w_i and the goal is maximum total weight of non-overlapping intervals, the greedy fails. Counterexample: intervals (0,10, w=10), (0,5, w=6), (5,10, w=6). Greedy by finish time picks (0,5) and (5,10), total weight 12. Optimum: pick (0, 10) alone, weight 10. Wait — that’s worse. Let me reconstruct: (0,10, w=100), (0,5, w=6), (5,10, w=6). Now greedy picks (0,5) and (5,10) for weight 12; optimum is (0,10) for weight 100.

The right approach is dynamic programming. Sort by finish time; for each interval i, define p(i) = the largest index j < i such that interval j finishes before i starts (compatible predecessor). Then:

OPT(i) = max( OPT(i-1),                       # skip interval i
              w_i + OPT(p(i)) )                # take interval i

The recurrence runs in O(n log n) total (the p(i) lookup is binary search per i). This is the classic Kleinberg-Tardos §6.1 worked example. It’s fundamentally DP — the optimal substructure includes a “skip vs take” branch that greedy can’t see. See 01 Knapsack for the conceptual neighbor (DP for selection problems with weights).

8.2 Interval Partitioning (Resource Allocation)

Variant: instead of one room, you have unlimited rooms and want the minimum number of rooms to schedule all activities. This is interval graph coloring: minimum colors such that no two overlapping intervals share a color. Greedy: sort by start time; for each interval, assign the lowest-numbered room that’s currently free; track per-room free-times in a min-heap. O(n log n). The minimum number of rooms equals the maximum depth of overlap — i.e., the maximum number of intervals containing any given point. (LeetCode 253 — Meeting Rooms II.)

8.3 Job Scheduling with Deadlines

Each job has a deadline d_i and a profit p_i; each takes unit time; maximize profit. Greedy: sort jobs by profit descending; for each, schedule it in the latest free slot ≤ d_i. O(n²) straightforward; O(n α(n)) with Union-Find. Different problem flavor (deadlines, not intervals), but same greedy spirit.

8.4 Group Activities by Conflict Graph

Modeling activities as nodes and overlaps as edges, the activity-selection problem is maximum independent set in an interval graph. Maximum independent set is NP-hard for general graphs but polynomial for interval graphs — and the polynomial algorithm is precisely earliest-finish-greedy. This is why the structure of interval graphs (a class with strong greedy properties — also chordal, perfect, etc.) is what makes the problem tractable.

8.5 Online Interval Scheduling

If intervals arrive one at a time and you must commit to “accept or reject” without seeing the future, no algorithm can guarantee the offline optimum. The competitive-ratio bound is 2 — there’s an algorithm achieving 2× optimal in the worst case, and no algorithm beats it. (See “online scheduling” literature; Borodin-El Yaniv “Online Computation and Competitive Analysis” Ch. 11.)

9. Common Interview Problems

LeetCode #	Title	Twist
435	Non-overlapping Intervals	Min removals = n - max kept
452	Minimum Number of Arrows to Burst Balloons	Same greedy; closed intervals (> not >=)
253	Meeting Rooms II	Interval partitioning, not selection
56	Merge Intervals	Different problem (merge, not select)
1235	Maximum Profit in Job Scheduling	Weighted version → DP
646	Maximum Length of Pair Chain	Direct activity-selection
1326	Minimum Number of Taps to Open to Water a Garden	Interval cover (related but distinct)

10. Pitfalls

10.1 Sorting by the Wrong Key

The single most common mistake. Sorting by start, by length, by reverse-finish, by midpoint — each fails on some constructible input. Always sort by finish time ascending for the activity-selection / non-overlapping-intervals family.

10.2 Treating the Weighted Variant as Greedy

If intervals carry weights and you want maximum total weight, do not sort-by-finish-greedy. The problem is fundamentally DP (see §8.1). Confusing the two is the most common interview blunder in this area; if the problem mentions a value/weight per interval, your immediate flag is “this is DP, not greedy.”

10.3 > vs >= (Open vs Closed Intervals)

For half-open intervals [s, f), two intervals at …ends at t and …starts at t do not overlap → use >=. For closed intervals [s, f], they touch at t → use >. Always state the convention and adjust the comparison accordingly. LC 252/253 use touching is allowed (closed intervals don’t conflict at endpoints by problem statement); LC 435 uses touching is allowed; LC 452 uses touching pops the balloon (closed, >-style). Read the problem statement carefully.

10.4 Forgetting to Handle Empty Input

return 0 or return [] for empty input is the safe default. max(...) or intervals[0] on empty input raises an exception — guard it.

10.5 Modifying Input in Place

intervals.sort() mutates the caller’s list. If the caller still needs the original order (or shouldn’t see ordering changes), use sorted(intervals, …) instead. Trivial, but a common silent contract violation in production code.

10.6 Using Floats for Tie-Breaking

If start/finish times are floats, comparison ties at the boundary become unreliable due to floating-point representation. Either use integer time encoding (e.g., minutes since midnight) or add an explicit epsilon-tolerance comparison.

10.7 Greedy on the Wrong Quantity

A subtle trap: “I want to maximize total time scheduled” is not the activity-selection problem — it’s a different problem (minimum-weight interval cover, or maximum-weight independent set if intervals are weighted by length). Don’t reflexively reach for sort-by-finish if the objective isn’t “maximum count of intervals.”

10.8 Confusing “Activity Selection” with “Interval Merging”

LC 56 (Merge Intervals) is a different problem with a different greedy (sort by start, then walk and merge overlapping). If a problem asks “merge overlapping intervals into the union,” that’s interval merging, not activity selection.

11. Diagram — The Greedy Walk

flowchart LR
    Sort["Sort by finish time ascending"] --> Init["last_finish = -∞<br/>selected = []"]
    Init --> Loop{For each (s, f) in sorted order}
    Loop -- "s ≥ last_finish" --> Take["selected.append((s, f))<br/>last_finish = f"]
    Loop -- "s < last_finish" --> Skip["skip — overlaps with last taken"]
    Take --> Loop
    Skip --> Loop
    Loop -- done --> Out["Return selected<br/>(maximum-cardinality non-overlapping set)"]

What this diagram shows. The control flow has exactly one decision per interval — does this interval start at-or-after the last taken interval's finish? If yes, take it (and update the threshold). If no, skip. The threshold last_finish only moves forward (it’s monotonically non-decreasing), and each forward move is exactly the smallest possible (because we’re considering intervals in finish-time order). That’s the geometric intuition behind the exchange argument: we’re always advancing the cursor by the smallest amount that keeps a non-overlapping set valid, which leaves the most space for future picks.

12. Open Questions

• Why does the problem-class admit a polynomial greedy at all? Because interval graphs have a special structure (they are perfect graphs and chordal), and maximum independent set in perfect graphs is polynomial. The activity-selection greedy is the constructive proof for the interval-graph subclass.
• Is there an O(n) algorithm if input is given in a smarter format? Yes — if intervals come pre-sorted by finish, the algorithm is O(n). There’s no way to beat the Ω(n log n) lower bound on unsorted input in the comparison model.

13. See Also

• Huffman Coding — sister provably-correct greedy with exchange-argument proof
• Kruskal’s Algorithm — sister greedy with cut-property proof
• Greedy Algorithms — Proof Techniques — meta-note on exchange/staying-ahead proofs
• 01 Knapsack — the weighted-selection problem requires DP
• Binary Search — used by the weighted-interval-scheduling DP for p(i) lookup
• Two Heaps Pattern — heap-based scheduling cousin
• Big-O Notation
• SWE Interview Preparation MOC