Activity Selection Problem: Complete Solution and Analysis

1. Introduction and Core Concepts

The activity selection problem is a foundational optimization problem in computer science that exemplifies the power and elegance of greedy algorithms. At its core, the problem asks a deceptively simple question: given a set of activities, each with a start time and a finish time, how can we select the maximum number of mutually compatible activities that can be performed by a single person or resource? Two activities are considered compatible if their time intervals do not overlap, meaning one finishes before the other starts.

This problem is formally defined as follows: Let S = {a1, a2, ..., an} be a set of n activities. Each activity ai is characterized by a start time si and a finish time fi, where 0 <= si < fi. A subset of activities is compatible if for any two activities ai and aj in the subset, their intervals [si, fi) and [sj, fj) do not overlap. The objective is to find a compatible subset of maximum cardinality. Unlike many optimization problems that require examining all possible combinations, the activity selection problem possesses a special structure that allows a greedy strategy to yield an optimal solution.

Understanding this problem matters far beyond the classroom because it models a ubiquitous class of resource allocation challenges. Any scenario involving a single, non-shareable resource that must be scheduled among competing requests maps directly to activity selection. From CPU scheduling and meeting room booking to satellite communication windows and manufacturing job sequencing, the ability to maximize throughput with a simple, efficient algorithm is invaluable. It also serves as the gateway to understanding more complex interval scheduling variants, including weighted scheduling and interval partitioning, making it an essential concept for every software engineer, systems designer, and algorithm enthusiast.

Why Greedy Works Here

Most optimization problems do not admit a greedy solution, but the activity selection problem exhibits two critical properties that make greediness optimal: the greedy-choice property and optimal substructure. The greedy-choice property means that a globally optimal solution can be assembled by making a locally optimal choice at each step. For activity selection, choosing the activity that finishes earliest is always safe; there exists an optimal solution that includes this choice.

Optimal substructure means that an optimal solution to the problem contains within it optimal solutions to subproblems. After selecting the earliest-finishing activity, the remaining problem is simply the activity selection problem on the subset of activities that start after the chosen activity finishes. This recursive structure allows us to build the solution incrementally without ever needing to reconsider previous decisions, which is the hallmark of a greedy algorithm and the reason it achieves such remarkable efficiency.

2. How It Works

The mechanism behind the activity selection algorithm is elegantly simple and operates in two logical phases: sorting and selection. First, all activities are sorted in monotonically increasing order of their finish times. If two activities have the same finish time, they can be ordered arbitrarily, though tie-breaking by start time is common. This sorting step is crucial because it establishes the order in which the greedy choice will be applied.

Once sorted, the selection phase proceeds iteratively. The algorithm always selects the first activity in the sorted list, as it has the earliest finish time. It then iterates through the remaining activities in order, selecting an activity if and only if its start time is greater than or equal to the finish time of the last selected activity. This condition ensures compatibility. By always picking the activity that leaves the maximum remaining time for future activities, the algorithm maximizes the number of activities that can be accommodated.

Consider the intuition: an activity that finishes early leaves more room for other activities than one that finishes late. Therefore, to maximize the count, we should be as conservative as possible with our time resource. This strategy is provably optimal through an exchange argument. Suppose we have an optimal solution that does not include the earliest-finishing activity, say ak. We can replace the first activity in that optimal solution with ak without reducing the number of activities or creating a conflict, because ak finishes no later than the activity it replaces. Repeating this exchange demonstrates that the greedy solution is at least as good as any optimal solution.

The Greedy Choice Proof Sketch

Formally, let the activities be sorted by finish time so that f1 <= f2 <= ... <= fn. Let a1 be the activity with the earliest finish time. Let S_k be the set of activities that start after ak finishes. The key theorem states that if A is an optimal solution for the original set S, and ak is the earliest-finishing activity, then there exists an optimal solution A' that includes ak. This is proven by taking any optimal solution A, looking at its earliest-finishing activity aj, and showing that (A - {aj}) U {ak} is also optimal and compatible. Since ak finishes earliest, it cannot conflict with any activity in A except possibly aj, so the exchange is valid.

This property allows us to reduce the problem recursively: after picking a1, the remaining problem is to solve activity selection for the set S' = {ai in S : si >= f1}. The optimal solution to S is then {a1} union the optimal solution to S'. Because the greedy choice is always part of some optimal solution, we never need to backtrack. This is fundamentally different from dynamic programming approaches where multiple choices must be explored and compared.

3. Implementation

Implementing the activity selection problem in Python is straightforward and highlights the algorithm's efficiency. The most common approach is iterative, requiring only a sort and a single linear scan. Below are several implementations demonstrating different styles and extensions, from the classic iterative solution to recursive and object-oriented variants.

The standard iterative implementation assumes the input is a list of tuples or lists where each element is (start, finish). It sorts the activities by finish time and then greedily builds the result set. This version is preferred in production and interviews due to its clarity and optimal performance.

# Classic Iterative Greedy Solution
def activity_selection(activities):
    """
    Selects maximum number of non-overlapping activities.
    activities: List of [start, finish] pairs
    Returns: List of selected activities
    """
    if not activities:
        return []

    # Sort activities by finish time - O(n log n)
    activities_sorted = sorted(activities, key=lambda x: x[1])

    selected = [activities_sorted[0]]
    last_finish = activities_sorted[0][1]

    # Single linear scan - O(n)
    for i in range(1, len(activities_sorted)):
        start, finish = activities_sorted[i]
        # If this activity starts after last selected finishes, select it
        if start >= last_finish:
            selected.append(activities_sorted[i])
            last_finish = finish

    return selected

# Example usage
activities = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]]
print(activity_selection(activities))
# Output: [[1, 4], [5, 7], [8, 11], [12, 16]]

A recursive formulation more closely mirrors the mathematical definition of optimal substructure and is useful for understanding the theoretical underpinnings. While it has the same time complexity, it uses additional stack space and is less common in practice for large inputs.

# Recursive Greedy Solution
def recursive_activity_selector(activities, k, n, last_finish):
    """
    Recursive helper for activity selection.
    activities: sorted by finish time
    k: current index to consider
    n: total number of activities
    last_finish: finish time of last selected activity
    """
    m = k + 1
    # Find the next compatible activity
    while m < n and activities[m][0] < last_finish:
        m += 1

    if m < n:
        # Include activities[m] and recurse for the rest
        return [activities[m]] + recursive_activity_selector(activities, m, n, activities[m][1])
    else:
        return []

def activity_selection_recursive(activities):
    if not activities:
        return []
    activities_sorted = sorted(activities, key=lambda x: x[1])
    # Always select the first activity (earliest finish)
    first = activities_sorted[0]
    rest = recursive_activity_selector(activities_sorted, 0, len(activities_sorted), first[1])
    return [first] + rest

For larger codebases, an object-oriented approach using dataclasses improves readability, type safety, and maintainability. This version also handles activities with names or IDs, which is common in real-world scheduling systems.

from dataclasses import dataclass
from typing import List

@dataclass
class Activity:
    name: str
    start: int
    finish: int

def activity_selection_oop(activities: List[Activity]) -> List[Activity]:
    """
    OOP version with named activities.
    Returns maximum set of compatible activities.
    """
    if not activities:
        return []

    # Sort by finish time
    sorted_acts = sorted(activities, key=lambda a: a.finish)

    selected = [sorted_acts[0]]
    last_finish = sorted_acts[0].finish

    for act in sorted_acts[1:]:
        if act.start >= last_finish:
            selected.append(act)
            last_finish = act.finish

    return selected

# Example with named activities
acts = [
    Activity("A", 1, 4),
    Activity("B", 3, 5),
    Activity("C", 0, 6),
    Activity("D", 5, 7),
    Activity("E", 8, 11)
]
result = activity_selection_oop(acts)
for r in result:
    print(f"{r.name}: [{r.start}, {r.finish})")

It is also instructive to implement a brute-force solution for comparison, especially for testing and for understanding why the greedy approach is necessary. The brute-force method checks all 2^n subsets, which quickly becomes infeasible.

# Brute Force for Verification (Exponential - Do Not Use for Large n)
def is_compatible(subset):
    """Check if all activities in subset are mutually compatible."""
    sorted_subset = sorted(subset, key=lambda x: x[0])
    for i in range(1, len(sorted_subset)):
        if sorted_subset[i][0] < sorted_subset[i-1][1]:
            return False
    return True

def brute_force_activity_selection(activities):
    """Finds optimal solution by checking all subsets - O(2^n * n log n)"""
    n = len(activities)
    best = []
    # Iterate through all 2^n subsets using bitmask
    for mask in range(1 << n):
        subset = [activities[i] for i in range(n) if mask & (1 << i)]
        if is_compatible(subset) and len(subset) > len(best):
            best = subset
    return sorted(best, key=lambda x: x[1])

4. Step-by-Step Example

To solidify understanding, let us walk through a concrete example in detail. Consider the following set of 11 activities, each represented as [start, finish). This is a classic example often used in textbooks like CLRS.

Initial unsorted set S = {a1=[1,4], a2=[3,5], a3=[0,6], a4=[5,7], a5=[3,9], a6=[5,9], a7=[6,10], a8=[8,11], a9=[8,12], a10=[2,14], a11=[12,16]}. Our goal is to find the largest compatible subset.

Step 1 is to sort all activities by finish time in non-decreasing order. After sorting, we obtain: a1=[1,4] (f=4), a2=[3,5] (f=5), a3=[0,6] (f=6), a4=[5,7] (f=7), a5=[3,9] (f=9), a6=[5,9] (f=9), a7=[6,10] (f=10), a8=[8,11] (f=11), a9=[8,12] (f=12), a10=[2,14] (f=14), a11=[12,16] (f=16). The sorted order is critical; without it, the greedy choice fails.

Step 2 is the greedy selection scan. We initialize our selected set with the first activity in the sorted list: Selected = {a1=[1,4]}, last_finish = 4. We then examine each subsequent activity in order. a2=[3,5] has start 3 < 4, so it conflicts with a1 and is skipped. a3=[0,6] has start 0 < 4, skipped. a4=[5,7] has start 5 >= 4, so it is compatible. We select it: Selected = {a1, a4}, last_finish = 7.

Continuing the scan: a5=[3,9] starts at 3 < 7, skipped. a6=[5,9] starts at 5 < 7, skipped. a7=[6,10] starts at 6 < 7, skipped. a8=[8,11] starts at 8 >= 7, so it is compatible and selected: Selected = {a1, a4, a8}, last_finish = 11. Next, a9=[8,12] starts at 8 < 11, skipped. a10=[2,14] starts at 2 < 11, skipped. Finally, a11=[12,16] starts at 12 >= 11, so it is selected: Selected = {a1, a4, a8, a11}.

The final optimal solution contains 4 activities: [1,4], [5,7], [8,11], and [12,16]. No other compatible subset can contain more than 4 activities from this set. Notice how the algorithm never needed to look ahead or reconsider a decision. Each choice was final. If we had instead chosen a different strategy, such as picking the shortest activity first or the earliest start time first, we would have obtained a suboptimal result. For instance, picking the shortest activity might select [3,5] (length 2) first, which would block [1,4] and lead to a smaller overall set.

5. Complexity Analysis

The efficiency of the activity selection algorithm is one of its most compelling features. Its time complexity is dominated by the sorting step, making it highly scalable even for large datasets. Understanding the precise complexity in best, average, and worst cases is essential for system design and performance prediction.

The algorithm consists of two distinct phases. The sorting phase, using an optimal comparison-based sort like Timsort in Python or Mergesort, takes O(n log n) time. The selection phase is a single linear scan through the sorted list, taking O(n) time. Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n). If the input is already sorted by finish time, the complexity reduces to O(n), which is the best case.

Space complexity is also efficient. The iterative version requires O(1) auxiliary space beyond the input storage and the output list, or O(n) if we count the output. The recursive version requires O(n) stack space in the worst case due to recursion depth. The brute-force alternative, by contrast, requires O(2^n) time and is completely impractical for n > 30.

It is important to distinguish between the unweighted and weighted variants. The unweighted version discussed here is solvable greedily in O(n log n). The weighted variant, where each activity has a value and the goal is to maximize total value, cannot be solved greedily and requires dynamic programming with O(n log n) time after sorting, or O(n^2) with a naive DP.

For practical purposes, the O(n log n) greedy solution is optimal. No algorithm can solve the general problem faster than O(n log n) in the comparison model, because sorting is a lower bound. If finish times are integers within a small range, counting sort or radix sort could theoretically reduce sorting to O(n), yielding an overall O(n) solution, but this is a specialized optimization.

6. Variations and Optimizations

While the classic activity selection problem is well-defined, numerous important variations arise in practice that require different techniques or optimizations. Understanding these variants is crucial for adapting the core idea to real-world constraints.

The most significant variation is the Weighted Activity Selection Problem. Here, each activity ai has a value or weight wi, and the goal is to maximize the total weight of the selected compatible activities, not just the count. The greedy strategy of picking the earliest finish time fails for this variant. A counterexample is easy to construct: one long, high-value activity might be better than two short, low-value ones. This problem requires dynamic programming. After sorting by finish time, we compute for each activity p(i), the last activity that is compatible with i. Then we define DP[i] as the maximum weight achievable using activities 1..i, with the recurrence DP[i] = max(DP[i-1], wi + DP[p(i)]). This yields an O(n log n) solution with binary search for p(i).

Another common variant is Activity Selection with Multiple Resources, also known as Interval Partitioning. Instead of one resource, we have k identical resources and want to schedule all activities using the minimum number of resources, or maximize throughput with k resources. This is solved by a different greedy algorithm using a min-heap to track resource availability. A related problem is scheduling to maximize the number of activities with k resources, which can be solved with a greedy algorithm that sorts by start time and uses a priority queue.

Additional variations include activities with flexible durations, activities that can be preempted, and online activity selection where activities arrive over time and decisions must be made without knowledge of future activities. For the online version, no deterministic algorithm can be optimal, and competitive analysis is used to evaluate performance. Optimizations for the classic problem focus on efficient implementation: if activities are given as a stream already sorted, we can process them in O(1) space without storing all of them, and if we only need the count and not the actual set, we can avoid storing the selected list.

Handling Edge Cases and Large Inputs

For very large n, such as millions of activities in log processing, memory and I/O become bottlenecks. An external sorting approach may be needed, and the selection scan can be performed in a streaming fashion. Using iterators and generators in Python allows processing without loading the entire sorted list into memory at once. Furthermore, if activities are defined by start and duration rather than start and finish, a simple preprocessing step to compute finish times is required.

7. Real-World Applications

Despite its academic appearance, the activity selection problem directly models a wide array of real-world systems where a single exclusive resource must be allocated efficiently. Its applications span computing, operations research, and everyday scheduling.

In operating systems and web servers, CPU scheduling and request handling often reduce to activity selection. A single CPU core can only execute one process at a time. When processes have known execution windows, maximizing throughput means selecting the maximum number of non-overlapping processes. Similarly, a web server handling long-polling connections or a database handling exclusive locks on a table must serialize access. Activity selection provides the optimal schedule for maximizing the number of requests served without conflicts.

In networking and telecommunications, the problem appears in channel allocation. A single communication channel, such as a satellite transponder or a wireless frequency band, can only carry one transmission at a time. Given requests with specific time windows, the provider wants to maximize the number of transmissions. The same logic applies to classroom or conference room booking systems, where the goal is to accommodate the maximum number of meetings in a single room, and to manufacturing where a single machine must process jobs with fixed time intervals.

Beyond direct scheduling, the greedy insight influences other domains. In bioinformatics, selecting the maximum number of non-overlapping genetic markers, and in finance, selecting the maximum number of non-overlapping trades on a single asset, both map to this problem. The algorithm's simplicity makes it ideal for embedded systems and real-time schedulers where computational overhead must be minimal and decisions must be made quickly with limited memory.

8. Comparison with Alternatives

Choosing the right algorithm depends on the precise problem constraints. The greedy activity selection algorithm is optimal for the unweighted case, but alternative approaches are necessary when weights, multiple resources, or other constraints are introduced. Understanding the trade-offs is essential for correct system design.

Dynamic Programming is the primary alternative for the weighted variant. It guarantees optimality for weighted cases but is overkill for the unweighted case, adding unnecessary complexity and a slightly higher constant factor. Brute Force enumeration is only useful for verification on tiny inputs or for educational purposes to demonstrate exponential blowup. Interval Partitioning solves a different objective: minimizing the number of resources needed to schedule all activities, rather than maximizing the number scheduled on one resource.

Another related problem is Interval Scheduling with Earliest Start Time or Shortest Duration heuristics. These are also greedy strategies but they are not optimal for maximizing count. For example, picking the shortest interval first can be shown to fail with a simple counterexample where a short interval in the middle blocks two other intervals that together would yield a larger set. Only the earliest finish time heuristic is provably optimal for the unweighted maximum cardinality objective.

In summary, if your problem is to maximize the number of compatible activities on a single resource and all activities are equally valuable, the greedy earliest-finish-time algorithm is the undisputed best choice due to its simplicity and efficiency. If activities have different values, you must use dynamic programming. If you need to schedule all activities with the fewest resources, use interval partitioning. Never use brute force beyond n < 25, and never use shortest-duration or earliest-start heuristics if optimality is required.

9. Common Mistakes and Best Practices

Even though the algorithm is simple, developers and students frequently make subtle errors that lead to incorrect or inefficient implementations. Awareness of these pitfalls is critical for both interviews and production code.

The most common mistake is sorting by the wrong key. Sorting by start time or by duration instead of finish time does not yield an optimal solution. For example, consider activities [1,10], [2,3], [4,5]. Sorting by start time picks [1,10] first and then cannot pick anything else, yielding a set of size 1, while the optimal solution is {[2,3], [4,5]} of size 2. Sorting by duration picks [2,3] first, which happens to be optimal in this case, but there are counterexamples where shortest duration also fails. Always sort by finish time for the unweighted maximum cardinality problem.

Another frequent error is mishandling the compatibility condition. The condition should be start >= last_finish if intervals are defined as [start, finish) where finish is exclusive, or start > last_finish if intervals are inclusive. Using the wrong inequality can either incorrectly allow overlapping activities or incorrectly reject compatible ones. Be consistent with the interval definition used in the problem statement. Additionally, failing to handle edge cases such as an empty input list, a single activity, activities with identical finish times, or activities with zero duration can cause runtime errors or incorrect outputs.

A third pitfall is assuming the greedy approach works for the weighted case. Many novices apply the same earliest-finish-time logic to weighted activities and get a suboptimal answer. It is essential to recognize when the problem variant changes the required technique. For weighted activities, you must switch to dynamic programming.

Best Practices

• Always sort explicitly: Do not assume input is sorted. Explicitly sort by finish time at the start of your function, and document this requirement.
• Use stable and efficient sorting: In Python, use sorted() with key=lambda x: x[1] which is O(n log n) and stable.
• Handle ties deterministically: When finish times are equal, consider sorting secondarily by start time to make behavior predictable.
• Validate input: Check that start < finish for all activities and handle negative times if applicable.
• Write pure functions: Avoid mutating the original list; return a new list of selected activities.
• Test with counterexamples: Test your implementation against known cases where alternative heuristics fail to ensure correctness.
• Document interval semantics: Clearly state whether intervals are [s, f) or [s, f] to avoid off-by-one errors.

For production systems, consider using named tuples or dataclasses for clarity, adding type hints, and writing unit tests that cover empty inputs, fully overlapping inputs, fully non-overlapping inputs, and large random inputs compared against a brute-force solution for small n to verify correctness.

10. Interview Questions

The activity selection problem is a staple of technical interviews because it tests understanding of greedy algorithms, proof techniques, and complexity analysis. Below are common interview questions and how to approach them effectively.

Q1: Explain why the greedy choice of picking the activity with the earliest finish time is optimal. Can you prove it? This question tests your ability to articulate the exchange argument. A strong answer will state the greedy-choice property and optimal substructure, then walk through the proof: assume an optimal solution A, let aj be its earliest-finishing activity, and let ak be the globally earliest-finishing activity. Show that (A - {aj}) U {ak} is also optimal and compatible because fk <= fj. Conclude that there exists an optimal solution containing the greedy choice, so the choice is safe. Mention that this can be applied inductively to prove overall optimality.

Q2: What is the time and space complexity of your solution? Can you do better than O(n log n)? The expected answer is O(n log n) time due to sorting and O(n) or O(1) auxiliary space. Explain that if the input is already sorted, it is O(n). Discuss the lower bound: any comparison-based algorithm must take Omega(n log n) because sorting is reducible to activity selection. Mention that with non-comparison sorting like counting sort for bounded integer times, O(n) is possible, but in the general comparison model, O(n log n) is optimal.

Q3: How would you modify your solution if each activity has a profit/value and you want to maximize total profit? This is the weighted activity selection variant. The correct answer is to explain that the greedy approach fails and that dynamic programming is required. Outline the steps: sort by finish time, compute p(i) for each i using binary search, define DP[i] = max(DP[i-1], value[i] + DP[p(i)]), and reconstruct the solution by backtracking. State the complexity as O(n log n) time and O(n) space. Providing a counterexample where greedy fails for weighted case demonstrates deep understanding.

Q4: Given a set of activities, how would you find the minimum number of rooms/resources needed to schedule all activities without overlap? This is the interval partitioning problem, a common follow-up. The solution is a different greedy algorithm: sort activities by start time, maintain a min-heap of end times of allocated resources, iterate through activities, and if the earliest finishing resource is free (heap top <= current start), reuse it, otherwise allocate a new resource. The number of resources is the heap size. Complexity is O(n log n). This tests whether you can distinguish between maximizing count on one resource versus minimizing resources for all activities.

Q5: Implement activity selection to return both the maximum count and the actual selected activities. How do you handle activities with the same finish time? This is a coding question. The interviewer expects clean code that sorts by finish time, iterates, and collects results, handling edge cases like empty input. For ties, explain that any order among equal finish times yields an optimal count, but for determinism you can sort by start time secondarily. Write code with proper variable names, handle start >= last_finish correctly, and mention testing. Be prepared to trace through an example and discuss that the solution may not be unique; multiple optimal sets may exist.

Mastering these questions requires not just memorizing the algorithm, but understanding its proof, limitations, and variants. Practice implementing both iterative and recursive versions, and be ready to discuss trade-offs and real-world applications to demonstrate comprehensive knowledge.