Greedy Algorithms: The Quest for Optimal Choice — Inspired by The Lord of the Rings

The Quest Begins (The "Why")

I still remember the first time I faced an interview question that felt like trying to solve a Rubik’s Cube blindfolded. The prompt was simple: given a list of meeting start and end times, pick the maximum number of non‑overlapping meetings you can attend. My brain went straight to “let’s try every combination” – a classic brute‑force approach that exploded in O(2ⁿ) time. After a few minutes of scribbling on a whiteboard, I realized I was chasing a dragon with a toothpick.

That frustration sparked a question: Is there a smarter way to make locally good choices that somehow add up to a globally optimal solution? The answer, as it turns out, lives in the world of greedy algorithms. And once you see the pattern, a whole class of scheduling, packing, and resource‑allocation problems becomes tractable.

The Revelation (The Insight)

The core idea of a greedy algorithm is beautifully simple: make the choice that looks best right now, and never look back. It sounds almost too naive, but for certain problems that local optimum is guaranteed to be part of some global optimum.

Why does it work for the activity‑selection problem? Imagine you’re standing at the start of a timeline. If you always pick the activity that finishes the earliest, you leave the maximum possible room for the rest of the day. Any other choice that finishes later can only shrink the remaining time window, never enlarge it. This “earliest‑finish‑time” rule is a matroid property: the set of activities forms a matroid where the greedy algorithm is optimal.

Proof sketch (the kind you can whiteboard in an interview):

1. Let A be the set of activities selected by the greedy algorithm, ordered by finish time.
2. Let O be an optimal solution, also ordered by finish time.
3. We show by induction that after each step, the greedy choice is compatible with some optimal solution.
   • Base: The first greedy activity finishes no later than the first activity in O (otherwise we could swap them and still have a feasible solution).
   • Inductive step: Assume the first k greedy activities fit inside an optimal solution. The (k+1)‑st greedy activity finishes earliest among all activities that start after the k‑th greedy activity finishes. If O uses a different activity at this spot, we can replace it with the greedy one without losing feasibility or optimality.

Thus, after n steps, the greedy solution is optimal.

The beauty? The algorithm runs in O(n log n) time if we need to sort by finish time, or O(n) if the input is already sorted. No DP tables, no recursion, just a single pass.

Wielding the Power (Code & Examples)

The Struggle (Brute‑Force / DP Attempt)

def activity_selection_brute(activities):
    # activities = [(start, end), ...]
    n = len(activities)
    best = 0

    def backtrack(i, last_end, count):
        nonlocal best
        if i == n:
            best = max(best, count)
            return
        # skip current
        backtrack(i+1, last_end, count)
        # take current if it fits
        s, e = activities[i]
        if s >= last_end:
            backtrack(i+1, e, count+1)

    backtrack(0, float('-inf'), 0)
    return best

This explores every subset – exponential time. For n = 20 it’s already sluggish; for n = 100 it’s hopeless.

The Victory (Greedy)

def activity_selection_greedy(activities):
    """
    activities: list of (start, end) tuples.
    Returns the maximum number of non‑overlapping activities.
    """
    # 1. Sort by finishing time (earliest first)
    activities.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    for start, end in activities:
        if start >= last_end:          # compatible with what we've taken
            count += 1
            last_end = end             # update the boundary

    return count

Why this works: The sorting step guarantees we always consider the activity that frees up the timeline the soonest. The loop then picks it if it doesn’t clash with the last chosen activity.

Common traps to avoid:

• Forgetting to sort – the greedy choice only holds when we process by earliest finish time.
• Using start time as the sorting key – that can lead to sub‑optimal packs (think of a short activity that starts early but ends late, blocking many others).
• Assuming the algorithm works for weighted intervals – it doesn’t; you need DP there.

A Second Interview Flavor

Another classic that yields to the same pattern is minimum number of cameras to monitor a binary tree (LeetCode 968). The greedy insight: place cameras as high as possible, starting from the leaves and moving upward. The algorithm runs in O(n) time with a single post‑order traversal.

def minCameraCover(root):
    # states: 0 = needs camera, 1 = has camera, 2 = covered
    def dfs(node):
        if not node:
            return 2                     # null nodes are considered covered
        left = dfs(node.left)
        right = dfs(node.right)

        if left == 0 or right == 0:      # a child needs a camera
            self.ans += 1
            return 1                     # this node gets a camera
        if left == 1 or right == 1:      # a child has a camera
            return 2                     # this node is covered
        return 0                         # otherwise, this node needs a camera

    self.ans = 0
    if dfs(root) == 0:                   # root needs a camera
        self.ans += 1
    return self.ans

Again, the greedy rule (“place a camera only when a child is uncovered”) yields an optimal solution with linear time.

Why This New Power Matters

Mastering this greedy pattern does more than let you ace interview questions – it equips you with a mental toolkit for real‑world systems. Think of scheduling jobs on a CPU, allocating bandwidth in a network, or even deciding which tasks to batch in a CI pipeline. When you can spot the “earliest finish” or “leave the most room” property, you replace heavyweight DP or backtracking with a clean, linear‑time pass.

The confidence boost is real: you stop fearing combinatorial explosions and start seeing opportunities to simplify. And the best part? The code is short enough to fit on a sticky note, yet powerful enough to handle thousands of items in a blink.

Your Turn

Here’s a challenge: take the activity‑selection problem and twist it slightly – each activity now has a profit, and you want to maximize total profit while still respecting non‑overlap. Does the greedy “earliest finish” still work? If not, can you think of a hybrid approach that keeps the spirit of greediness but adds a twist?

Drop your thoughts in the comments, or better yet, write a quick script and see where the intuition leads you. Happy coding, and may your algorithms always find the optimal path!