Greedy Like a Jedi: Picking Activities the Smart Way

The Quest Begins (The "Why")

I still remember the first time I stared at a coding interview question that asked me to schedule the maximum number of non‑overlapping meetings in a single day. My brain went straight to brute force: try every subset, check overlaps, keep the biggest. The answer was correct, but the runtime exploded as soon as the input grew beyond a dozen items. I felt like I was trying to defeat a final boss by swinging a wooden sword—lots of effort, zero progress.

That frustration sparked a simple question: Is there a smarter way to look at the problem? Turns out, the answer lives in a greedy strategy that feels almost like a cheat code once you see it.

The Revelation (The Insight)

The activity‑selection problem is a classic: you have a list of activities, each with a start time s[i] and a finish time f[i]. You want to pick the largest possible subset of activities that don’t overlap.

The greedy insight is deceptively simple: always pick the activity that finishes earliest, then repeat the process on the remaining activities that start after it finishes.

Why does that work? Two properties guarantee optimality:

1. Greedy‑choice property – picking the earliest‑finishing activity leaves the maximum possible room for the rest. If you chose any other activity that finishes later, you’d only shrink the available time window, never enlarge it.
2. Optimal substructure – after you take that first activity, the problem reduces to the same kind of problem on the remaining activities (those that start after the chosen one finishes).

Think of it like clearing a path through a dense forest: you always step onto the clearing that appears soonest, guaranteeing you’ll never backtrack into a dead‑end. Once you accept that the earliest finish is the best first move, the rest follows naturally.

Wielding the Power (Code & Examples)

The Naïve Attempt (the struggle)

def max_activities_brute(activities):
    # activities = [(start, finish), ...]
    from itertools import combinations
    best = 0
    for r in range(len(activities) + 1):
        for combo in combinations(activities, r):
            if all(combo[i][1] <= combo[i+1][0] for i in range(len(combo)-1)):
                best = max(best, len(combo))
    return best

This checks every subset—O(2ⁿ * n log n) after sorting each combo. For n = 20 it’s already sluggish; for n = 100 it’s hopeless.

The Greedy Victory

def max_activities_greedy(activities):
    # Sort by finish time (earliest first)
    activities.sort(key=lambda x: x[1])
    count = 0
    last_finish = float('-inf')
    for start, finish in activities:
        if start >= last_finish:          # no overlap with the last chosen activity
            count += 1
            last_finish = finish
    return count

What changed?

1. Sorting – O(n log n). After that, a single linear scan does the work.
2. The loop – O(n). We keep only the finish time of the last selected activity and greedily take whatever fits next.

Common traps to avoid:

• Sorting by start time – feels intuitive but fails because an early‑starting long activity can block many short ones that finish sooner.
• Forgetting to update last_finish – you’ll end up counting overlapping activities.
• Assuming the input is already sorted – always sort; the guarantee relies on the order.

Let’s see it in action with a typical interview scenario:

Problem: You’re given a list of lecture halls with their start and end times. Find the maximum number of lectures you can attend without overlap.

lectures = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7), (8, 9)]
print(max_activities_greedy(lectures))   # → 4

The optimal set is (1,3) → (4,6) → (6,8) → (8,9). The greedy scan picks exactly those.

A Second Twist: Weighted Intervals?

If each activity had a profit and you wanted maximum profit, greedy no longer works—you’d need DP. But for the plain count version, the earliest‑finish rule is provably optimal and blazingly fast.

Why This New Power Matters

Mastering this pattern does more than solve a single interview question. It trains you to spot greedy‑choice opportunities everywhere:

• Coin change (when denominations are canonical).
• Huffman coding (building an optimal prefix tree).
• Minimizing maximum lateness (schedule tasks by earliest deadline).

When you recognize that a problem exhibits the greedy‑choice property and optimal substructure, you can replace exponential searches with a simple sort‑and‑scan, turning an impossible‑looking constraint into a smooth O(n log n) solution.

The confidence boost is real. I once walked into a whiteboard interview, scribbled the sorting line, ran through the loop, and watched the interviewer’s eyes light up. “That’s it?” they asked. I smiled and said, “Yep—just pick the earliest finisher and keep going.” The offer followed shortly after.

Your Turn

Here’s a mini‑quest for you:

Challenge: Given a list of projects, each with a start day and an end day (inclusive), return the maximum number of projects you can complete if you can only work on one project at a time.

Try implementing the greedy solution, test it on random data, and notice how the runtime stays linear after the sort. If you get stuck, remember: look for the earliest finish, take it, and repeat.

Go ahead, give it a shot, and share your results in the comments. I can’t wait to see how you wield this new power!