Greedy

What it is

A greedy algorithm builds a solution through a sequence of locally preferred choices. Instead of exploring every possible continuation, it commits to a choice that can be justified as safe: some optimal solution remains possible after that choice.

The benefit is reduced search. A subset problem may have exponentially many candidates, while a greedy solution might only sort the inputs and scan them once. The difficult part is not implementing the choice; it is proving that the choice preserves optimality.

A useful distinction is between feasibility and optimality. Feasibility means the chosen objects satisfy the constraints. Optimality means no other feasible solution has a better objective. A greedy algorithm needs both.

Greedy is not synonymous with “take the largest” or “take the cheapest.” The correct preference depends on the objective and on how a choice restricts future choices.

How to recognize it

Look for these signals:

• Selection under a simple budget: each item has a cost, and every selected item contributes the same benefit.
• Intervals on a line: choices depend on starts, finishes, overlap, or coverage.
• Ordering matters: the same jobs or tasks produce different costs when rearranged.
• One-sided construction constraints: the next value must satisfy a lower bound or a condition involving its predecessor.
• A sorted prefix becomes infeasible: one retained item can be removed to restore feasibility.
• A natural exchange: replacing one choice with another improves the objective without damaging the remaining solution.

These signals suggest a candidate strategy, not a proof. Different objectives can require different rules on the same input. Finishing intervals early helps select many nonoverlapping intervals; selecting an endpoint helps cover intervals with points.

Be cautious when decisions have complicated dependencies, values differ independently from costs, or a locally attractive choice can block several better choices. Those features often require dynamic programming or another approach.

The core technique

1. Sort by a provably useful priority

Use this variant when a global ordering turns the problem into a simple scan.

For independent items with nonnegative costs and equal benefit, taking the cheapest items first maximizes the number affordable. Any selection of k items costs at least as much as the k cheapest items.

def choose_items(costs, budget):
    chosen = []
    for i in sorted(range(len(costs)),
                    key=lambda i: (costs[i], i)):
        if costs[i] > budget:
            break
        budget -= costs[i]
        chosen.append(i)
    return chosen

Sorting by index after cost makes ties deterministic. It also chooses the smallest indices among equal-cost alternatives. Here, the greedy prefix minimizes cost among maximum-cardinality selections.

For ordering objectives, use an adjacent-exchange argument. Compare placing task a before task b against the reverse order, keeping everything else fixed.

For minimizing weighted completion time, with duration p and positive weight w, placing a first is no worse exactly when:

p_a * w_b <= p_b * w_a

Thus sort by increasing p / w. Prefer exact cross-product comparisons over floating-point ratios, and break equal-ratio ties consistently. This rule assumes all tasks are available initially and execute without interruption on one machine.

Another standard ordering variant concerns two processing stages: every job visits stage one and then stage two, and each stage handles one job at a time. To minimize final completion time, place jobs with first-stage duration no greater than second-stage duration first, sorted by increasing first-stage duration. Place the remaining jobs afterward, sorted by decreasing second-stage duration. The rule is specific to this two-stage model, not general scheduling.

2. Make interval choices at the decisive endpoint

For maximum-cardinality selection of nonoverlapping intervals, sort by increasing finish time. Accept an interval whenever it is compatible with the last accepted interval. An earlier finish leaves at least as much room for future intervals as a later finish.

For covering closed intervals with the fewest points, use the same sorting order but a different action: when an interval is uncovered, choose its right endpoint.

def cover_intervals(intervals):
    points = []
    for left, right in sorted(intervals,
                              key=lambda interval: interval[1]):
        if not points or points[-1] < left:
            points.append(right)
    return points

Why the right endpoint? The earliest-ending uncovered interval requires a point somewhere inside it. Moving that point to its right endpoint cannot lose coverage of any remaining interval that the original point covered: remaining intervals end no earlier.

For integer intervals requiring several distinct selected points, a related strategy processes right endpoints and adds missing points as far right as possible. Existing selections must be counted before adding more. Efficient implementations require suitable counting and predecessor-search structures; the endpoint rule alone does not determine runtime.

3. Construct the smallest feasible prefix

Use this variant when choosing a larger current value cannot improve future feasibility or reduce future cost.

Suppose output values must satisfy x[i] >= lower[i] and x[i] >= x[i-1] + gap, for a fixed nonnegative gap. Choose:

x[i] = max(lower[i], x[i-1] + gap)

Start with x[0] = lower[0]. This minimizes every prefix coordinate, and therefore the total increase above the lower bounds.

The proof is induction: every feasible first value is at least the greedy first value. If another feasible predecessor is no smaller, its next value must also be at least the greedy next value. Choosing extra slack now only raises, or leaves unchanged, later lower bounds.

This reasoning fails if larger current choices can unlock discounts or other future benefits.

4. Keep choices provisional with a heap

Some greedy algorithms revise earlier choices rather than commit permanently.

To maximize the number of independent tasks completed by their deadlines on one machine, sort by deadline. Retain each task provisionally. If total duration exceeds the current deadline, remove the longest retained task.

import heapq

def maximum_task_count(tasks):
    total = 0
    retained = []
    for duration, deadline in sorted(tasks,
                                      key=lambda task: task[1]):
        total += duration
        heapq.heappush(retained, -duration)
        if total > deadline:
            total += heapq.heappop(retained)
    return len(retained)

Removing the longest task frees the most time while sacrificing only one task. The retained tasks remain feasible in deadline order. This rule assumes nonnegative durations, initial availability, and equal benefit per completed task; it does not maximize arbitrary task weights.

Common mistakes

• Skipping the proof: test an exchange argument, a prefix invariant, or a lower bound before trusting examples.
• Confusing objectives: maximum count, minimum cost, and minimum completion time need different rules.
• Ignoring assumptions: release times, negative costs, dependencies, or unequal rewards can invalidate a strategy.
• Mishandling endpoints: closed intervals contain both endpoints; half-open intervals use different compatibility tests.
• Treating tie-breaking as cosmetic: secondary or lexicographic objectives need their own justification.
• Using inaccurate comparisons: ratio sorting should avoid rounding errors and, in fixed-width languages, multiplication overflow.
• Losing reconstruction data: heaps storing only durations can return a count, but returning selected tasks requires identifiers.

Complexity

Sorting-based greedy algorithms typically take O(n log n) time for sorting and O(n) for scanning. Already sorted inputs may reduce the total to O(n).

The lower-bound sequence construction takes O(n) time and O(1) auxiliary space, excluding its output.

Heap-based selection takes O(n log n) time: each task is inserted once and removed at most once. The heap uses O(n) space.

Auxiliary space for sorting depends on the implementation. Output lists use space proportional to their size. More elaborate interval counting variants add the costs of their data structures; a greedy proof establishes correctness, not automatically a linear-time implementation.