15. Greedy Algorithms

Introduction to Greedy Algorithms

Greedy algorithms solve optimization problems by making a sequence of choices, each of which looks best at the moment. The key idea is that a locally optimal choice (the best choice among the currently available options) leads to a globally optimal solution for problems that possess two important properties:

• Greedy‑choice property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
• Optimal substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

These properties distinguish greedy methods from dynamic programming (DP). While DP explores many possibilities and stores subproblem results to avoid recomputation, a greedy algorithm makes an irrevocable decision at each step and never looks back. This often yields simpler algorithms with lower time complexity, but it is only correct when the problem satisfies the above properties.

The typical steps for designing a greedy algorithm are:

1. Define the problem and identify a suitable greedy criterion (e.g., earliest finish time, highest value‑to‑weight ratio).
2. Sort the input according to that criterion if needed.
3. Iteratively select the next element that satisfies the greedy rule, update the solution state, and reduce the remaining problem.
4. Repeat until no more elements can be added.

In the following sections we examine four canonical problems that illustrate these steps: activity selection, fractional knapsack, Huffman coding, and job sequencing with deadlines.

Activity Selection Problem

Problem Statement

Given n activities, each with a start time s_i and a finish time f_i (where s_i < f_i), select the maximum number of mutually non‑overlapping activities. Two activities i and j are compatible if s_i >= f_j or s_j >= f_i.

Greedy Strategy

The optimal greedy choice is to always pick the activity that finishes earliest among those that are compatible with the already selected set. By sorting activities by increasing finish time, we can simply scan the list and pick each activity whose start time is not earlier than the finish time of the last selected activity.

Pseudocode

sort activities by f_i ascending
A = {first activity}
last_finish = f_first
for each activity i in sorted list:
    if s_i >= last_finish:
        A.add(i)
        last_finish = f_i
return A

Proof of Correctness (Exchange Argument)

Let O be an optimal solution and G the greedy solution. Consider the first activity where O and G differ. Since the greedy algorithm picks the activity with the earliest finish time that is compatible with previously chosen activities, the activity chosen by the greedy algorithm finishes no later than the activity chosen by O at that position. By exchanging the activity in O with the greedy choice we obtain another optimal solution that is not worse than O and agrees with G on one more position. Repeating this exchange yields an optimal solution identical to G. Hence the greedy algorithm is optimal.

Example

Consider the following activities (start, finish):

Sorted by finish time we obtain the order: 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). Applying the greedy scan:

• Select A1 (finish = 4).
• A2 starts at 3 < 4 → skip.
• A3 starts at 0 < 4 → skip.
• A4 starts at 5 ≥ 4 → select A4 (finish = 7).
• A5 starts at 3 < 7 → skip.
• A6 starts at 5 < 7 → skip.
• A7 starts at 6 < 7 → skip.
• A8 starts at 8 ≥ 7 → select A8 (finish = 11).
• A9 starts at 8 < 11 → skip.
• A10 starts at 2 < 11 → skip.
• A11 starts at 12 ≥ 11 → select A11 (finish = 16).

The selected activities are A1, A4, A8, A11 corresponding to (1,4), (5,7), (8,11), (12,16), yielding a maximum of 4 non‑overlapping activities.

Fractional Knapsack Problem

Problem Statement

Given a knapsack with capacity W and n items, each item i has a value v_i and weight w_i. Unlike the 0/1 knapsack, we may take any fraction 0 ≤ x_i ≤ 1 of an item, gaining value x_i·v_i and consuming weight x_i·w_i. The goal is to maximize total value without exceeding capacity.

Greedy Metric

The optimal greedy choice is to consider items in decreasing order of their value‑to‑weight ratio ρ_i = v_i / w_i. Intuitively, items that give the most value per unit weight should be taken first.

Algorithm

sort items by ρ_i = v_i / w_i descending
total_value = 0
remaining = W
for each item i in sorted list:
    if w_i <= remaining:
        take whole item
        total_value += v_i
        remaining -= w_i
    else:
        fraction = remaining / w_i
        total_value += fraction * v_i
        remaining = 0
        break
return total_value

Complexity Analysis

Sorting dominates the running time: O(n log n). The subsequent scan is linear, O(n). Hence overall complexity is O(n log n).

Example

Capacity W = 50. Items:

Sorted by ratio: I1, I2, I3.

• Take I1 wholly: weight = 10, value = 60, remaining capacity = 40.
• Take I2 wholly: weight = 20, value = 100, remaining capacity = 20.
• I3 weight = 30 > remaining = 20 → take fraction 20/30 = 2/3 of I3.
• Value from fraction = (2/3)·120 = 80.

Total value = 60 + 100 + 80 = 240. The knapsack is full (weight = 10+20+20 = 50).

Huffman Coding

Problem Statement

Given a set of symbols with their frequencies (or probabilities), construct a binary prefix‑free code (no code is a prefix of another) that minimizes the expected code length, i.e., the weighted sum Σ f_i·l_i where f_i is the frequency of symbol i and l_i is the length of its code.

Greedy Strategy

Huffman’s algorithm repeatedly merges the two symbols (or sub‑trees) with the smallest frequencies. The intuition is that symbols that occur less frequently should receive longer codes, while frequent symbols get shorter codes. By always combining the two lowest‑frequency nodes, we guarantee an optimal tree.

Steps

1. Create a leaf node for each symbol, storing its frequency.
2. Insert all leaf nodes into a min‑heap (priority queue) keyed by frequency.
3. While the heap contains more than one node:
   • Extract the two nodes x and y with smallest frequencies.
   • Create a new internal node z with frequency f_z = f_x + f_y.
   • Make x and y the left and right children of z (assign 0 to left edge, 1 to right edge).
   • Insert z back into the heap.
4. The remaining node is the root of the Huffman tree. Traverse the tree to assign binary codes (0 for left, 1 for right).

Complexity

Each heap operation costs O(log n). With n‑1 merges, total time is O(n log n). Space usage is O(n) for the heap and tree nodes.

Example

Symbol frequencies: A(5), B(9), C(12), D(13), E(16), F(45).

Step‑by‑step merging (showing frequencies):

• Combine A(5) + B(9) → node AB(14).
• Combine C(12) + D(13) → node CD(25).
• Combine AB(14) + E(16) → node ABE(30).
• Combine CD(25) + ABE(30) → node CDEAB(55).
• Combine F(45) + CDEAB(55) → root(100).

Resulting codes (0 = left, 1 = right):

The expected length is minimized; any other prefix code would have a larger weighted sum.

Job Sequencing with Deadlines (Job Scheduling)

Problem Statement

We have n jobs. Each job i yields a profit p_i if completed before its deadline d_i. Each job takes exactly one unit of time, and at most one job can be scheduled in any time slot. The objective is to select a subset of jobs and assign them to distinct time slots ≤ their deadlines to maximize total profit.

Greedy Strategy

Sort jobs in descending order of profit. For each job, place it in the latest available time slot that is ≤ its deadline. This leaves earlier slots open for potentially other (lower‑profit) jobs, thereby maximizing the chance to accommodate more jobs.

To efficiently find the latest free slot we use a disjoint‑set (union‑find) data structure where each slot initially points to itself; after a slot is occupied we union it with the previous slot.

Pseudocode

sort jobs by profit descending
max_deadline = max(d_i for all i)
make-set(i) for i = 0 .. max_deadline   // parent[i] = i
total_profit = 0
for each job (p, d) in sorted list:
    available = find(d)          // returns greatest free slot ≤ d
    if available > 0:
        total_profit += p
        union(available, available-1)   // mark slot as used
return total_profit

Complexity Analysis

Sorting takes O(n log n). Each find and union operation runs in amortized O(α(n)) time, where α is the inverse Ackermann function (practically constant). Hence overall complexity is O(n log n + n·α(n)) ≈ O(n log n).

Example

Jobs (profit, deadline):

Sorted by profit: J1(100,2), J3(27,2), J4(25,1), J2(19,1), J5(15,3).

Initially all slots 0…3 are free.

• J1: find(2) → slot 2 free → schedule J1 at slot 2, union(2,1). Profit = 100.
• J3: find(2) → now find returns slot 1 (since 2 is occupied) → schedule J3 at slot 1, union(1,0). Profit = 127.
• J4: find(1) → slot 0 (since 1 occupied) → but slot 0 is a dummy (no time), so find returns 0 → cannot schedule.
• J2: find(1) → returns 0 → cannot schedule.
• J5: find(3) → slot 3 free → schedule J5 at slot 3, union(3,2). Profit = 142.

Final schedule: slot 2 → J1 (100), slot 1 → J3 (27), slot 3 → J5 (15). Total profit = 142. No better profit is achievable.

Summary and When to Use Greedy

Greedy algorithms are powerful when a problem exhibits the greedy‑choice property and optimal substructure. They often lead to simple, efficient solutions with O(n log n) or linear time after sorting. However, correctness is not guaranteed for arbitrary problems; one must prove (typically via an exchange argument) that the greedy choice never harms optimality.

The four problems covered in this chapter illustrate the paradigm:

• Activity selection – earliest finish time yields maximum cardinality of compatible intervals.
• Fractional knapsack – value‑to‑weight ratio guides fractional picks.
• Huffman coding – repeatedly merging the two lowest‑frequency nodes builds an optimal prefix code.
• Job sequencing with deadlines – profit‑ordered placement in the latest free slot maximizes profit.

When encountering a new optimization problem, consider whether a natural greedy criterion exists and whether exchanging a greedy choice with any optimal solution can be shown to preserve optimality. If so, a greedy algorithm is likely the right approach.