Greedy Algorithms

Greedy algorithms select a locally preferred choice, commit to it, and solve the remaining smaller instance. Their implementations are often short; their central obligation is a proof that the commitment preserves access to a global optimum. Without that proof, a plausible local rule is only a heuristic.

For one-resource interval selection, consider (0,10),(1,2),(2,3),(3,4), with an interval allowed to start when the previous one finishes. “Choose the earliest start” commits to (0,10) and returns one activity. “Choose the earliest finish” selects the three short intervals. The example does not prove earliest finish correct, but it immediately refutes one plausible rule and exposes the resource that matters: how much timeline remains after a choice. Greedy design alternates between such counterexamples and a structural proof.

Greedy Choice

A greedy optimization needs two properties:

1. Optimal substructure — after a safe choice, the remaining decisions form a smaller instance whose optimum completes the original optimum.
2. Greedy-choice property — some globally optimal solution begins with the locally selected choice, so committing to it cannot exclude every optimum.

The second property is what permits early commitment. In 0–1 knapsack it fails: the highest-value or highest-density item can consume capacity needed by a better combination. Dynamic programming retains competing states when no safe commitment proof exists. Greedy and DP are therefore alternative consequences of different structural proofs, not interchangeable coding styles.

Proof Techniques

A greedy implementation is often short because the proof has already done the hard work. Three proof shapes recur.

Exchange Arguments

Take an arbitrary optimal solution that disagrees with the greedy choice. Replace its first conflicting choice by the greedy one, prove feasibility is preserved and objective value does not worsen, then repeat. The transformation establishes that some optimum begins greedily; optimal substructure handles the remainder.

Staying Ahead

Compare the greedy partial solution with any competing partial solution after every step. If the greedy solution is never behind under a carefully chosen measure, no competitor can finish better. For earliest-finish interval selection, after selecting k activities, the greedy schedule’s last finish time is no later than that of any feasible k-activity schedule. Therefore it always leaves at least as much room for future choices.

Cut Properties

Partition a structure into completed and uncompleted regions. Prove the lightest or safest choice crossing that boundary belongs to some optimum. Minimum spanning trees use this directly: the lightest edge crossing a cut that respects chosen edges is safe. A cut proof is an exchange argument expressed through graph structure.

All three techniques identify the exact property a counterexample would need to violate. If the exchange introduces conflict, the staying-ahead measure reverses, or a cut choice is not truly lightest, the proposed rule has not been justified.

Activity Selection

Given n activities with start and finish times and one resource, select a maximum-cardinality subset of nonoverlapping activities.

Several local rules are plausible:

• Earliest start can choose one long activity that blocks several short ones.
• Shortest duration can occupy a central interval and block compatible activities on both sides.
• Earliest finish is safe because it leaves at least as much remaining time as any alternative first choice.

#include <stdlib.h>

typedef struct {
    int start;
    int finish;
} Activity;

int compare_by_finish(const void *a, const void *b) {
    const Activity *left = a;
    const Activity *right = b;
    if (left->finish < right->finish) {
        return -1;
    }
    if (left->finish > right->finish) {
        return 1;
    }
    if (left->start < right->start) {
        return -1;
    }
    if (left->start > right->start) {
        return 1;
    }
    return 0;
}

/* Selects a maximum set of non-overlapping activities; returns how many were chosen,
   and fills `chosen` with their indices into the (now finish-time-sorted) array. */
size_t select_activities(Activity acts[], size_t n, size_t chosen[]) {
    if (n == 0U) {
        return 0U;
    }
    qsort(acts, n, sizeof(Activity), compare_by_finish);

    chosen[0] = 0U;
    size_t count = 1U;
    int last_finish = acts[0].finish;

    for (size_t i = 1; i < n; i++) {
        if (acts[i].start >= last_finish) {   /* no overlap with the last chosen activity */
            chosen[count++] = i;
            last_finish = acts[i].finish;
        }
    }
    return count;
}

The function requires writable acts and chosen arrays of at least n elements when n > 0, and every activity must satisfy start <= finish; it returns zero without dereferencing the arrays when n == 0. Sorting costs O(n log n), and the selection pass costs Theta(n).

For finish-sorted activities (1,4),(3,5),(0,6),(5,7),(5,9),(8,9), the scan proceeds as follows:

The result has three activities.

Exchange Argument

An exchange argument transforms an arbitrary optimum so that it contains the greedy choice:

Take an optimal solution. If it omits the greedy choice, replace one conflicting choice with the greedy one while preserving feasibility and objective value. The transformed solution is an optimum containing the greedy choice.

Let S be an optimal schedule, let a be its first activity, and let g be the globally earliest-finishing activity. Since g.finish <= a.finish, replacing a by g cannot conflict with any later activity in S. The replacement preserves cardinality, so the result is also optimal and contains g.

After selecting g, discard every overlapping activity. The remaining compatible activities form the same problem on a smaller set. Applying the exchange argument repeatedly proves the complete greedy schedule optimal. The proof fails for earliest start because replacing an optimum’s first activity by an earlier-starting but later-finishing interval can introduce conflicts.

Scheduling

Activity selection maximizes the number of nonoverlapping jobs on one resource. Interval partitioning asks a different question: assign every interval to a resource while minimizing the number of resources—classrooms, platforms, processors, or meeting rooms.

Sort intervals by start time. Maintain a min-priority queue keyed by each resource’s latest finish time. For the next interval:

• if the earliest-finishing resource is free, reuse it;
• otherwise create a new resource;
• update that resource’s finish time.

sort intervals by start time
for interval (start,finish):
    if heap not empty and minimum finish <= start:
        resource = extract minimum
    else:
        resource = create new
    assign interval to resource
    insert (finish,resource)

When the algorithm creates resource d, the new interval overlaps the d-1 intervals currently occupying all existing resources. These d mutually simultaneous intervals prove every schedule needs at least d resources. The algorithm uses exactly that many, so it is optimal. Sorting and heap operations take O(n log n) time and O(n) space.

For start-sorted intervals (0,4),(1,3),(3,5),(4,7),(5,6), let a heap entry be finish:resource:

The schedule uses two resources. At time just after 1, intervals (0,4) and (1,3) overlap, certifying that one resource is impossible. The heap is not merely an efficiency device: its minimum identifies the only existing resource that could become available earliest; if that one is still busy, every other resource is busy too.

Endpoint semantics matter. If an interval ending at time t is compatible with one starting at t, use finish <= start; if both endpoints occupy the resource, use a strict comparison. This policy belongs in the problem specification.

Deadline Scheduling

Another scheduling objective leads to a different rule. Each job j has processing time p_j and deadline d_j; all jobs are available at time zero and must run non-preemptively on one machine. If job j completes at time C_j, its lateness is L_j=C_j-d_j. The objective is to minimize maximum lateness L_max.

The optimal rule is earliest deadline first: sort jobs by nondecreasing deadline. Its proof uses adjacent exchange. Suppose a schedule contains consecutive jobs i then j with d_i > d_j, starting after prior work of length t. Before swapping,

After swapping them,

and

Thus the swap does not increase the maximum lateness of the pair and changes no later completion time. Repeatedly swapping deadline inversions transforms an optimum into earliest-deadline order without worsening it.

For jobs A=(p=3,d=8), B=(2,5), C=(4,9), and D=(1,3), deadline order is D,B,A,C. Completion times are 1,3,6,10, latenesses are -2,-2,-2,1, and L_max=1. Negative lateness means early completion; the objective minimizes the worst value rather than forcing every job to finish before its deadline.

This rule solves maximum lateness, not every deadline objective. Maximizing profit from a subset of deadline jobs, minimizing the number of late jobs, and handling release times have different structure and may require different greedy rules or dynamic programming.

Fractional Knapsack

In 0–1 knapsack, each item is indivisible. In fractional knapsack, any fraction of an item may be taken, and value scales linearly with the fraction. Divisibility makes decreasing value-per-weight order safe.

#include <stdbool.h>
#include <math.h>
#include <stddef.h>
#include <stdlib.h>

typedef struct {
    double weight;
    double value;
} Item;

int compare_by_ratio_desc(const void *a, const void *b) {
    const Item *ia = (const Item *) a;
    const Item *ib = (const Item *) b;
    double ra = ia->value / ia->weight;
    double rb = ib->value / ib->weight;
    if (ra < rb) {
        return 1;                      /* descending ratio */
    }
    if (ra > rb) {
        return -1;
    }
    return 0;
}

bool fractional_knapsack(Item items[], size_t n, double capacity,
                         double *out) {
    if (out == NULL || !isfinite(capacity) || capacity < 0.0 ||
        (n > 0U && items == NULL)) {
        return false;
    }
    for (size_t i = 0; i < n; i++) {
        if (!isfinite(items[i].weight) || items[i].weight <= 0.0 ||
            !isfinite(items[i].value) || items[i].value < 0.0 ||
            !isfinite(items[i].value / items[i].weight)) {
            return false;
        }
    }
    if (n > 1U) {
        qsort(items, n, sizeof(Item), compare_by_ratio_desc);
    }

    double total_value = 0.0;
    double remaining = capacity;

    for (size_t i = 0; i < n && remaining > 0.0; i++) {
        if (items[i].weight <= remaining) {
            total_value += items[i].value;
            remaining -= items[i].weight;
        } else {
            double fraction = remaining / items[i].weight;
            total_value += items[i].value * fraction;
            remaining = 0.0;
        }
        if (!isfinite(total_value)) {
            return false;
        }
    }
    *out = total_value;
    return true;
}

The function validates the classic problem’s domain: finite nonnegative values, finite positive weights, representable ratios, and finite nonnegative capacity. It mutates item order. Sorting costs O(n log n) and the scan costs Theta(n).

The exchange proof below is over exact real ratios. The C implementation instead solves a floating-point approximation: two distinct mathematical densities can round to the same double, and summation can accumulate rounding error. Its result should therefore be interpreted under the platform’s floating model, not as an exact rational optimum. When weights and values are exact integers or rationals and exact ordering matters, compare value_a * weight_b with value_b * weight_a using checked wider arithmetic or arbitrary precision, and represent the accumulated answer with a rational or an explicitly documented error bound.

Divisibility

Suppose an optimum leaves some amount of the highest-ratio item unused while taking positive weight from a lower-ratio item. Exchange an equal weight epsilon from the lower ratio to the higher ratio. Weight remains unchanged and value strictly increases, contradicting optimality. Therefore some optimum takes as much as possible from the highest ratio, after which the same argument applies to the remaining capacity.

The same exchange is illegal in 0–1 knapsack because an item cannot be traded fractionally. Divisibility is exactly the condition that makes density ordering safe. Removing it changes both the correctness proof and the appropriate algorithmic technique.

For items (weight,value)=(10,60),(20,100),(30,120) and capacity 50, density order with whole items takes the first two for value 160; taking the latter two gives 220. The counterexample isolates the lost divisibility assumption.

Huffman Coding

Huffman coding uses a different greedy choice: repeatedly combine the two least frequent symbols until one tree remains. The resulting prefix code minimizes frequency-weighted code length.

In a prefix-free code, no symbol’s bit string is a prefix of another’s, so a decoder can identify codeword boundaries without separators. If symbol i has frequency f_i and depth d_i, total encoded length is sum(f_i d_i). The objective is to minimize this weighted external path length.

Build a tree bottom-up. Start with one leaf per symbol, repeatedly merge the two smallest-frequency nodes, and assign their sum to the new parent. A root-to-leaf path gives the codeword, using 0 for a left edge and 1 for a right edge.

The following implementation isolates that greedy construction. It assumes n >= 1; chars and freqs contain n entries; frequencies are positive and their sum fits in int; all allocation-size expressions are representable; every allocation succeeds; and print_codes receives a path buffer of at least n bytes. A production API must report allocation failure and free every partially constructed tree.

#include <stdio.h>
#include <stdlib.h>

typedef struct HuffmanNode {
    char character;              /* meaningless for internal nodes */
    int frequency;
    struct HuffmanNode *left;
    struct HuffmanNode *right;
} HuffmanNode;

HuffmanNode *make_leaf(char c, int freq) {
    HuffmanNode *node = malloc(sizeof(HuffmanNode));
    node->character = c;
    node->frequency = freq;
    node->left = node->right = NULL;
    return node;
}

HuffmanNode *make_internal(HuffmanNode *left, HuffmanNode *right) {
    HuffmanNode *node = malloc(sizeof(HuffmanNode));
    node->character = '\0';
    node->frequency = left->frequency + right->frequency;
    node->left = left;
    node->right = right;
    return node;
}

/* Removes and returns the node with the smallest frequency from an unsorted array of pointers. */
HuffmanNode *extract_min(HuffmanNode *nodes[], int *count) {
    int min_index = 0;
    for (int i = 1; i < *count; i++) {
        if (nodes[i]->frequency < nodes[min_index]->frequency) {
            min_index = i;
        }
    }
    HuffmanNode *result = nodes[min_index];
    nodes[min_index] = nodes[--(*count)];     /* swap last element into the gap */
    return result;
}

HuffmanNode *build_huffman_tree(const char chars[], const int freqs[], int n) {
    HuffmanNode **nodes = malloc((size_t) n * sizeof(HuffmanNode *));
    for (int i = 0; i < n; i++) {
        nodes[i] = make_leaf(chars[i], freqs[i]);
    }

    int count = n;
    while (count > 1) {
        HuffmanNode *a = extract_min(nodes, &count);
        HuffmanNode *b = extract_min(nodes, &count);
        nodes[count++] = make_internal(a, b);    /* the merged pair becomes one new candidate */
    }

    HuffmanNode *root = nodes[0];
    free(nodes);
    return root;
}

void print_codes(const HuffmanNode *node, char *path, int depth) {
    if (!node->left && !node->right) {            /* a leaf: print its assigned code */
        path[depth] = '\0';
        printf("'%c': %s\n", node->character, path);
        return;
    }
    path[depth] = '0';
    print_codes(node->left, path, depth + 1);
    path[depth] = '1';
    print_codes(node->right, path, depth + 1);
}

extract_min scans the whole array per removal, so this array-based implementation builds the tree in O(n²) time. A min-heap supports each extraction and insertion in O(log n), reducing construction to O(n log n).

For one symbol, the root is already a leaf and print_codes emits an empty codeword. Formats that require at least one bit conventionally assign 0; that encoding policy is separate from tree optimality.

Merge Trace

For frequencies A:5, B:9, C:12, D:13, E:16, F:45, the priority queue evolves through these merges:

One left/right assignment yields F=0, C=100, D=101, A=1100, B=1101, and E=111. No codeword prefixes another because symbols occur only at leaves. The weighted cost is

The same cost equals the sum of merge weights 14+25+30+55+100. Each merge creates a parent and increases the depth of every leaf below it by one, adding exactly the merged subtree frequency to total code length. This identity provides a compact way to audit a constructed tree.

Huffman’s correctness follows from a sibling lemma and induction.

A full binary prefix-code tree has exactly two children at every internal node. With more than one positive-frequency symbol, some optimum is full: an internal node with one child can be bypassed, shortening every codeword below it without creating a prefix conflict. The sibling argument therefore works within full trees without excluding a better one-child shape.

1. In a full prefix-code tree, choose two sibling leaves at maximum depth. Exchanging their symbols with the two least-frequent symbols cannot increase weighted path length: moving smaller frequencies deeper and larger frequencies shallower is never worse. Therefore some optimal tree places the two least-frequent symbols as deepest siblings.
2. Merge those symbols x and y into a pseudo-symbol z with frequency f(z)=f(x)+f(y). Any code tree for the reduced alphabet expands into a tree for the original alphabet by replacing leaf z with two children. The expansion increases total cost by exactly f(x)+f(y), independent of the reduced tree’s shape.
3. If Huffman were nonoptimal for the original alphabet, its reduced tree would be nonoptimal for the merged alphabet; replacing it by a better reduced tree and expanding would produce a better original tree. By induction on alphabet size, recursively merging the two smallest frequencies yields an optimal prefix code.

With a binary min-heap, initialization is O(n), and the n-1 pairs of extractions and insertions cost O(log n) each, giving O(n log n) construction time. Code generation visits every tree node once; emitted bit-string volume adds output-dependent cost.

Matroid Structure

Some greedy theorems apply to an entire family of problems. An independence system consists of a finite ground set E and a family I of feasible subsets such that every subset of a feasible set is feasible. A matroid additionally satisfies the exchange axiom:

If A and B are feasible and |A| < |B|, some element of B-A can be added to A while preserving feasibility.

For nonnegative element weights, sorting elements by decreasing weight and adding an element whenever feasibility remains true produces a maximum-weight maximal independent set. To see why, compare greedy choices with an optimal set. Whenever the greedy set contains a heavier element absent from the optimum, the exchange axiom identifies an element that can be replaced while retaining feasibility and cardinality. Because processing order makes the greedy element at least as heavy, the exchange does not reduce optimal weight. Repeating aligns an optimum with the greedy set.

Examples include:

• uniform matroid: every subset of size at most k is feasible, so choose the k heaviest elements;
• partition matroid: elements are divided into categories with per-category quotas;
• graphic matroid: edges are feasible when they form a forest, making weight-ordered safe-edge selection the structure behind Kruskal’s algorithm.

Not every hereditary constraint is a matroid. Nonoverlapping interval sets can violate the exchange axiom: one long interval may be maximal while two short compatible intervals form a larger feasible set, with neither short interval addable to the long one. Unweighted activity selection still has a specialized earliest-finish proof, but arbitrary weighted interval scheduling needs dynamic programming. The structural axiom explains both the reach and the limit of generic greedy-by-weight reasoning.

Greedy Failures

• Coin change with arbitrary denominations. For {1,3,4} and target 6, largest-first chooses 4+1+1, while 3+3 uses fewer coins. Some currency systems support a largest-first theorem; arbitrary positive denominations do not. The input family is part of the claim.
• Longest simple path in a graph. “Walk to the most promising unvisited neighbor” has no optimality guarantee. The general longest-simple-path problem is NP-hard.
• 0–1 knapsack. Density order is valid only when fractions can be exchanged. Indivisible choices retain capacity interactions that require DP, exact search, or approximation.
• Earliest-start activity selection. The interval (0,10) blocks three compatible short intervals in the opening example. Starting early is not the objective; preserving room for future activities is.

Each failure lacks a safe exchange: a local choice can consume capacity, position, or connectivity needed by a better completion. Small counterexamples should be sought before a proof, but unsuccessful testing does not replace an exchange, staying-ahead, or cut argument.

Choosing Greedy

For a proposed greedy optimization, audit the following obligations:

1. Rule. State one deterministic, checkable choice criterion and its tie policy.
2. Counterexamples. Search small instances where the first greedy choice blocks a better completion.
3. Safety proof. Transform an arbitrary optimum to include the choice, prove a staying-ahead relation, or establish a cut property.
4. Residual problem. After fixing the choice, prove that the remaining decisions form the same problem with no hidden interaction.
5. If a proof fails, preserve the unresolved alternatives. Dynamic programming is appropriate when those alternatives collapse into a manageable state space with overlapping subproblems. Otherwise the problem may call for backtracking, branch-and-bound, a graph or flow formulation, an approximation, or an exact method with exponential worst-case cost.

Greedy Review

• Greedy algorithms commit to locally selected choices and require a proof that an optimum remains reachable.
• Exchange, staying-ahead, and cut arguments are recurring proof structures.
• Earliest finish time optimizes single-resource activity selection; earliest available resource optimizes interval partitioning.
• Value density is safe for fractional knapsack because items are divisible, but not for 0–1 knapsack.
• Huffman repeatedly merges the two least frequent symbols and is optimal by a sibling lemma plus induction.
• Counterexamples expose rules that merely resemble valid greedy algorithms.
• When no greedy-choice proof survives, dynamic programming or exact search may need to preserve alternatives.

Greedy Problems

Choice Traces

1. Run earliest-start, shortest-duration, and earliest-finish activity rules on one common interval set. Record the first choice that causes the results to diverge.
2. Trace interval partitioning on eight intervals with several equal endpoints. Show the heap after every assignment under both half-open and closed endpoint conventions.
3. Trace fractional knapsack on five items, including one fractional final item. Audit total weight and value under exact rational arithmetic and double arithmetic.
4. Build a Huffman tree for frequencies 2,3,7,9,18,25. List every merge, derive one code, and verify weighted path length by both leaf depths and merge-weight sum.

Exchange Proofs

5. Prove earliest-finish activity selection with an exchange argument, then restate the same result as a staying-ahead proof.
6. Prove interval partitioning uses exactly the maximum depth—the largest number of intervals covering one time point.
7. Formalize the equal-weight exchange for fractional knapsack. Identify every place that requires positive weights, linear divisibility, and exact ratio order.
8. Complete Huffman’s sibling lemma: show symbol exchanges cannot increase cost and show contraction preserves the difference between candidate tree costs.
9. Prove the cut property used by Kruskal or Prim as an exchange argument on spanning trees.

Counterexample Construction

10. Find smallest counterexamples to earliest-start activity selection, shortest-duration activity selection, largest-first coin change with {1,3,4}, and density-first 0–1 knapsack.
11. Give a graph where choosing the cheapest edge incident to the most recently added vertex fails to produce an MST. Explain why Prim’s global cut rule avoids the failure.
12. Construct an instance where a poor tie rule in a greedy implementation changes the returned solution but not its objective, and another where an unspecified tie rule invalidates correctness.
13. Determine whether selecting the two largest frequencies first can ever be optimal Huffman construction for three or more unequal positive frequencies. Prove or refute.

Greedy Implementations

14. Make select_activities non-mutating by sorting index records. Return original input indices and distinguish invalid intervals from allocation failure.
15. Implement train-platform allocation with arrival/departure events. Define event ordering when a departure and arrival share a timestamp and prove it matches the resource convention.
16. Replace Huffman’s array extraction with a binary min-heap, add complete allocation cleanup, and return codes without writing to stdout.
17. Implement exact density comparison for signed 64-bit values and positive 64-bit weights. Specify whether wider arithmetic, checked cross-products, or arbitrary precision supports the full domain.

Structural Decisions

18. Unit-time jobs have deadlines and profits. Analyze sorting by descending profit and placing each job in the latest free slot at or before its deadline. Supply a proof and an efficient disjoint-set implementation.
19. Design the greedy algorithm for minimizing maximum lateness when all jobs are available at time zero. State the scheduling order and prove it by swapping adjacent inversions.
20. Compare fractional and 0–1 knapsack on one input where their optima coincide and one where they differ sharply. Identify the precise exchange that indivisibility forbids.
21. A proposed rule for a new problem survives thousands of random tests but resists exchange, staying-ahead, and cut proofs. Describe how to turn the failed proof step into a systematic counterexample search and when to retain alternatives with DP or exact search.
22. Characterize a family of coin denominations for which largest-first is canonical, or prove correctness for one restricted family such as powers of a fixed base. Separate the theorem from empirical currency examples.