Activity Selection

#How does it work?

A greedy algorithm makes the choice that looks best right now at each step and never goes back. For some problems these local choices add up to the best overall solution; for others they don't. Proving which is the real difficulty of greedy algorithms.

In the activity selection problem, given activities with start and end times, we want the largest number of activities that don't overlap, for example in a single meeting room.

The right greedy rule: pick the activity that ends first, drop those that overlap it, and repeat with the rest. Finishing early frees the room soonest and leaves the most time. Rules such as "starts first" or "shortest first" can give wrong answers; the lesson shows one.

#Try it yourself

#Step by step

1. 01Sort the activities by end time.
2. 02Take the first activity; set the last end time to its end.
3. 03If the next activity starts at or after the last end time, take it and update the last end.
4. 04Otherwise skip it; continue to the end of the list.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

# (start, end) of each activity; numbered 1..11 in this order.
ACTIVITIES = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]


def select(activities: list) -> list:
    """Most activities that don't overlap: earliest finish first."""
    order = sorted(range(len(activities)), key=lambda i: activities[i][1])
    chosen, last_end = [], float("-inf")
    for i in order:
        start, end = activities[i]
        if start >= last_end:  # doesn't overlap the last one taken
            chosen.append(i + 1)
            last_end = end
    return chosen


chosen = select(ACTIVITIES)
print(len(chosen))
print(" ".join(map(str, chosen)))

#Complexity

Sorting dominates; the scan is a single pass. The rule is proven correct with an exchange argument: the first activity of any optimal solution can be swapped for the one that ends first, and the solution stays valid.

#When to use it?

Meeting room and resource booking, job scheduling on a CPU, ad slots and any scheduling problem where one resource is shared. If activities have different values (weighted interval scheduling), greedy isn't enough and DP is needed.

#Practice

Log in to answer questions and save your progress.