Unit 4: Greedy techniques

Greedy algorithms build a solution piece by piece, always choosing the option that looks best at the moment, and never reconsidering. They arose as a design paradigm alongside dynamic programming but trade completeness for speed: where DP explores overlapping subproblems, greedy commits immediately.

• Core mechanism: at each step select the locally optimal candidate by some fixed criterion, add it to the partial solution if feasible, and move on.
• Correctness prerequisites: a greedy strategy is provably correct only when the problem exhibits the greedy-choice property (a global optimum contains a locally optimal first choice) and optimal substructure (an optimal solution embeds optimal solutions to subproblems).
• Typical shape: sort or heap-order the input by the deciding key, then sweep once — giving common complexities of O(n log n) for sorting-based methods.
• Failure mode: when these properties fail (e.g. 0/1 knapsack, arbitrary coin systems), greedy yields a feasible but sub-optimal answer.

II. The Greedy Paradigm and Its Choice Rules

A. Greedy problem solving paradigm

A method that reaches a final answer through a sequence of irrevocable, locally best decisions.

• Design template: candidate set → selection function → feasibility check → objective function → solution check; each iteration picks and either keeps or discards one candidate.
• Contrast with DP: greedy makes one choice then solves one remaining subproblem; DP makes a choice only after solving all subproblems.
• Advantage: simple, fast, low memory — no table of states.

B. Locally optimal choice

The single decision that maximises (or minimises) the objective at the current step only.

• Definition: the candidate ranking highest under the selection function, ignoring all future consequences.
• Example: in coin change with {1,5,10,25} making 30, the locally optimal first pick is the 25-coin because it removes the most value now.
• Risk: local optimality is a heuristic — it becomes a proof only under the greedy-choice property.

C. Global optimal choice

The overall best solution across the entire problem, which greedy hopes to reach by chaining local choices.

• Definition: the feasible solution optimising the objective over the whole input.
• Bridge to local: an exchange argument shows any global optimum can be transformed, without loss, to start with the greedy local choice — establishing the two coincide.
• When they diverge: with coins {1,3,4} for value 6, local choices give 4+1+1 (3 coins) but the global optimum is 3+3 (2 coins).

III. Scheduling Problems

A. Job Sequencing problem

Schedule jobs, each with a deadline and profit, on a single machine (one job per unit time) to maximise profit.

• Strategy: sort jobs by profit descending; place each in the latest free slot at or before its deadline.
• Pseudocode:
  
  TEXT

  sort jobs by profit desc
  for each job j:
      for t = min(maxDeadline, j.deadline) down to 1:
          if slot[t] free: assign j to t; break

• Complexity: O(n²) naive, or O(n log n) with a disjoint-set for slot lookup.
• Worked example: jobs (d,p): A(2,100), B(1,19), C(2,27), D(1,25) → schedule C at t1? sort by profit: A,C,D,B → A→slot2, C→slot1, profit 127.

B. Job Selection problem

Choose a maximum-profit subset of jobs when jobs conflict in time, a selection (not ordering) task.

• Strategy: when only completion matters and each job occupies an interval, sort by finish time and greedily accept non-overlapping jobs.
• Distinction from sequencing: sequencing assigns time slots under deadlines; selection simply admits or rejects to avoid overlap.
• Objective: maximise count or profit of mutually compatible jobs.

C. Activity Selection problem

Select the largest set of activities that do not overlap, given start and finish times.

• Greedy rule: sort by finish time; repeatedly pick the next activity whose start ≥ last chosen finish.
• Why finish time: the activity ending earliest leaves the most room for the rest — the greedy-choice property here.
• Complexity: O(n log n).
• Worked example: activities (1,3),(2,5),(4,7),(6,8) → pick (1,3), then (4,7) → 2 activities selected.

IV. Array Product and Sum Problems

A. Maximum product subset of an array

Find the subset whose element product is largest.

• Rule: include every element except handle zeros and negatives:
  • Positives: always include.
  • Negatives: include all if their count is even; drop the largest (closest to 0) negative if the count is odd.
  • Zeros: exclude unless the array is a single 0 or all zeros/one negative.
• Example: [-1,-2,-3,0] → negatives count 3 (odd), drop -1 → product (-2)(-3)=6.

B. Minimum product subset of an array

Find the subset whose product is smallest (most negative or smallest positive).

• Rule: to minimise, keep exactly one negative sign when possible:
  • if there is at least one negative and at least one positive, or an even count of negatives, drop one negative to leave an odd (negative) product;
  • all positives: the minimum subset product is the smallest single element.
• Example: [-1,-2,-3] → include -1 and -2 → product 2? For minimum, take (-1)(-3)(-2) = -6 keeping all three (odd → negative). Minimum = -6.

C. Minimum sum of product of two arrays

Given arrays A and B of equal length, pair them to minimise Σ A[i]·B[i].

• Rearrangement inequality: the sum of products is minimised when one array is sorted ascending and the other descending.
• Steps: sort A ascending, B descending, then multiply term-by-term.
• Example: A=[1,2,3], B=[4,5,6] → pair 1·6+2·5+3·4 = 6+10+12 = 28 (minimum).

V. Resource-Packing Problems

A. Bin packing problem

Pack items of given sizes into the fewest unit-capacity bins — NP-hard, so greedy gives approximations.

• First Fit: place each item in the first bin it fits; O(n²), at most 2·OPT bins.
• First Fit Decreasing: sort sizes descending first, then First Fit; bound (11/9)·OPT + 1.
• Best Fit / Next Fit: Best Fit chooses the tightest bin; Next Fit only checks the current open bin (O(n), worse ratio).
• Example: sizes 0.5,0.7,0.5,0.2 cap 1 → FFD: 0.7+0.2, 0.5+0.5 → 2 bins.

B. Fractional Knapsack problem

Maximise value in a capacity-W sack where items may be taken in fractions.

• Greedy rule: sort items by value-per-weight ratio v/w descending; take whole items until one no longer fits, then take a fraction of it.
• Optimality: fractions permit exact capacity filling, so the greedy-choice property holds (unlike 0/1 knapsack).
• Complexity: O(n log n).
• Worked example: W=50, items (60,10),(100,20),(120,30) → ratios 6,5,4; take 10+20 fully (160, 30 wt used), then 20/30 of last → 160 + 120·(20/30) = 240.

VI. Cost-Minimisation with Priority Queues

A. Connect n ropes with minimum cost

Join ropes into one; joining two ropes costs the sum of their lengths — minimise total cost.

• Greedy rule: always connect the two shortest ropes first, using a min-heap.
• Why: shorter ropes joined early are re-added and counted in fewer subsequent sums (analogous to Huffman coding).
• Pseudocode:
  
  TEXT

  build min-heap of lengths
  while heap size > 1:
      a = extractMin; b = extractMin
      cost += a+b; insert(a+b)

• Example: [4,3,2,6] → 2+3=5, 4+5=9, 6+9=15 → total 5+9+15 = 29.

VII. Currency and Counting Problems

A. Coin change problem

Make a target amount using the fewest coins from given denominations.

1. Greedy version: repeatedly take the largest coin ≤ remaining amount — correct only for canonical systems like {1,5,10,25}.
2. Non-canonical failure: for {1,3,4} and amount 6, greedy gives 3 coins (4+1+1) but optimum is 2 (3+3), so DP is required for arbitrary systems.
   • Complexity: greedy O(amount / largest); correctness demands the denominations satisfy the greedy-choice property.

B. Problems based on greedy techniques

A family of tasks unified by "sort/heap then sweep once."

• Common signature: an objective separable per element and a proof that early local optima cannot block later ones.
• Representatives: minimum platforms for trains, Huffman encoding, Kruskal's and Prim's MST, minimising waiting time, largest number by concatenation.
• Diagnostic: attempt an exchange argument; if it fails, fall back to dynamic programming.

C. Majority Element

Find an element appearing more than n/2 times.

• Boyer–Moore voting: maintain a candidate and count; increment when the element matches, decrement otherwise, and reset the candidate when count hits 0.
• Greedy insight: each cancellation discards two distinct elements — a majority element survives all cancellations.
• Pseudocode:
  
  TEXT

  count = 0, cand = none
  for x in A:
      if count == 0: cand = x
      count += (x == cand) ? 1 : -1
  # verify cand occurs > n/2 times in a second pass

• Complexity: O(n) time, O(1) space; a verification pass is needed since not every array has a majority.
• Example: [2,2,1,1,1,2,2] → candidate settles on 2, which occurs 4 times > 3.5.