Greedy algorithms

Computer Science and Engineering (B.E./B.Tech) · Algorithms · free study notes for exams, placements and interviews

In short

A greedy algorithm builds a solution one step at a time, each time taking the choice that looks best right now and never undoing it. It is correct only when the problem has the greedy-choice property (a locally best first move is contained in some globally optimal solution) and optimal substructure; otherwise it gives a fast but wrong, or merely approximate, answer. The greedy method is a named unit in every AICTE/CBCS "Design and Analysis of Algorithms" course and appears in GATE CS almost every year through knapsack, Huffman codes, job sequencing and spanning-tree questions. In interviews at Amazon India, Flipkart, Walmart Global Tech, Zomato, Swiggy, Ola, Uber, Microsoft IDC, Google India and the service majors (TCS Digital, Infosys HackWithInfy, Wipro, Accenture), greedy interval and scheduling questions are standard, and the interviewer's real question is usually "prove your greedy is correct, or show me where it breaks".

Explained

What makes a problem solvable greedily

Greedy algorithm: at each step pick the candidate that maximises (or minimises) a *local* objective, commit to it irrevocably, and recurse on the smaller remaining problem.
Greedy-choice property: there exists an optimal solution that contains the first greedy choice. This is the step that must be *proved*, not assumed.
Optimal substructure: after fixing the greedy choice, an optimal solution to the remaining subproblem completes it to an optimal whole.
Why it is fast: no table, no recursion tree, no revisiting. Typically O(n log n) (dominated by one sort or by heap operations) and O(1)–O(n) extra space.
Greedy vs dynamic programming: DP explores *all* choices at each step and keeps the best, so it costs more but is safe; greedy makes *one* choice and never reconsiders. Greedy is DP with the branching factor forced to 1.
Greedy vs divide and conquer: D&C splits into independent subproblems of similar size; greedy peels off one element at a time, the subproblem shrinking by one.
Failure example to remember: coins {1, 3, 4}, amount 6 — greedy takes 4+1+1 (3 coins), optimum is 3+3 (2 coins). The same greedy *is* optimal on Indian currency (₹1, 2, 5, 10, 20, 50, 100, 200, 500) because that set is canonical; correctness depends on the denominations, not on the algorithm.

Designing and proving a greedy algorithm

Cast the problem as making a sequence of choices; list the plausible greedy criteria (smallest, largest, earliest finish, best value-per-weight, earliest deadline).
Sort or heapify by that criterion; prove the first choice is safe; prove the remainder is the same problem on fewer items; then write the loop.
Exchange argument (most used in exams): take any optimal solution O; if its first choice differs from the greedy choice g, swap g in for that element; show the result is still feasible and no worse. Repeating converts O into the greedy solution, so greedy is optimal. Used for activity selection, job sequencing and Kruskal.
"Greedy stays ahead" (induction): show that after each step the greedy partial solution is at least as good as any other partial solution on a chosen measure (e.g. after k activities, greedy's finish time is the earliest possible).
Matroid theory (the general theorem): if the feasible sets form a matroid — non-empty, hereditary (subsets of an independent set are independent) and satisfying the exchange property (|A| < |B| ⇒ some x ∈ B∖A keeps A ∪ {x} independent) — then the greedy algorithm on weights gives a maximum-weight independent set. Kruskal's algorithm is exactly greedy on the graphic matroid; job sequencing with deadlines is greedy on a transversal matroid.
Disproving a greedy: one small counter-example is a complete proof of incorrectness. Always test tiny inputs (n = 2, 3) and equal-key ties.

The classic greedy problems on the syllabus

Activity selection / interval scheduling (max number of non-overlapping intervals): sort by earliest finishing time, keep an activity if its start ≥ last chosen finish. O(n log n). Sorting by shortest duration or earliest start is *wrong*.
Interval partitioning (minimum platforms / meeting rooms): sort events; sweep arrivals and departures with two pointers (or a min-heap of finish times) and track the running count. The answer equals the maximum number of intervals overlapping at any instant — the "depth" lower bound, which greedy achieves.
Fractional knapsack: sort by value/weight ratio descending, fill whole items, break the last one into a fraction. Optimal, O(n log n) — O(n) with median-of-medians selection. The same ratio rule on 0/1 knapsack is not optimal (that needs DP).
Huffman coding: repeatedly merge the two least-frequent symbols into one node (min-heap); the resulting prefix-free binary tree minimises Σ fᵢ·dᵢ. O(n log n), or O(n) if frequencies arrive sorted (two-queue method). Produces a prefix code, so decoding needs no delimiters; it is optimal among symbol-by-symbol prefix codes.
Job sequencing with deadlines (unit-time jobs, maximise profit): sort jobs by profit descending; place each job in the latest free slot at or before its deadline; skip if none. O(n²) naively, O(n log n) with a disjoint-set "next free slot" structure.
Optimal merge pattern / "minimum cost to connect ropes" / optimal file merging: repeatedly merge the two smallest lists; total cost = sum of all internal node values = Σ (length × depth). Identical algorithm to Huffman.
Optimal storage on tapes (minimise mean retrieval time): store files in increasing length (SPT order); MRT = (1/n) Σ_{j=1..n} Σ_{i=1..j} lᵢ.
Coin / currency change: greedy by largest denomination ≤ remaining amount; optimal for canonical systems such as Indian notes and coins, not in general.
Other standard greedy exercises: fractional/continuous job allocation, minimum number of arrows to burst intervals, non-overlapping-interval removal, gas-station circular tour, candy/ratings distribution, Egyptian fraction representation, greedy graph colouring (uses at most Δ+1 colours but is not minimal), largest number from digits, and the two-pointer "maximise pairs" family.

Greedy inside graph algorithms (brief — detailed in their own notes)

Kruskal: sort edges by weight, add an edge if it joins two different components (disjoint-set union). Safe by the cut property.
Prim: grow one tree, repeatedly adding the cheapest edge leaving it (min-heap/decrease-key).
Dijkstra: repeatedly finalise the unvisited vertex with the smallest tentative distance — a greedy commitment that is valid only with non-negative edge weights; a negative edge can break it, because a later cheaper path can still arrive.
Each of these is greedy with a provable exchange argument; the proofs, complexities and variants belong to the spanning-tree and shortest-path notes.

Greedy results in scheduling (single machine, as examined)

SPT / SJF (shortest processing time first) minimises total and average completion time Σ Cⱼ (and hence average waiting time) on one machine.
EDF (earliest deadline first) minimises maximum lateness L_max = max(Cⱼ − dⱼ) when all jobs are available at time 0.
Moore–Hodgson rule minimises the *number* of late jobs: schedule in EDF order and, whenever a job becomes late, discard the longest job scheduled so far.
Deadline feasibility: a set of unit-time jobs is schedulable iff, for every t, the number of jobs with deadline ≤ t is ≤ t (Hall-type condition).
LPT (longest processing time first) for m identical machines gives makespan ≤ (4/3 − 1/(3m)) × optimum — a greedy *approximation*, since the exact problem is NP-hard.
Johnson's rule solves the two-machine flow shop optimally by a greedy ordering — usually taught in Operations Research rather than DAA.

When greedy can only approximate, and its limits

Set cover: repeatedly take the set covering the most uncovered elements → cost ≤ H(n) ≈ ln n + 1 times optimal; this is essentially the best possible unless P = NP.
Vertex cover: greedily picking both endpoints of an uncovered edge (maximal matching) gives a 2-approximation; picking the highest-degree vertex does *not* guarantee a constant factor.
0/1 knapsack: best of (ratio-greedy result, single most valuable fitting item) is a ½-approximation; ratio-greedy *alone* has no constant guarantee.
Metric TSP: the MST-doubling greedy tour is ≤ 2 × optimal; Christofides improves it to 1.5.
Advantages: simple to code and reason about, O(n log n) typical, O(1) auxiliary memory, works on streams and online inputs, easy to parallelise the sort.
Limitations: no backtracking, so one wrong commitment is permanent; correctness must be proved per problem; it cannot handle problems whose optimum needs combinations (0/1 knapsack, longest common subsequence, coin change on arbitrary denominations, graph colouring minimality); ties and floating-point ratio comparisons can silently change the answer.

Key points

Greedy algorithm - irrevocable locally-best choice at each step; no reconsideration.
Greedy-choice property - some optimal solution contains the first greedy pick; the thing to prove.
Optimal substructure - the rest of an optimal solution is optimal for the remaining subproblem.
Exchange argument - swap the greedy element into an arbitrary optimum without making it worse.
Greedy stays ahead - induction showing greedy's prefix dominates any rival prefix.
Matroid theorem - greedy gives the maximum-weight independent set exactly when the feasible sets form a matroid.
Activity selection - sort by earliest finish time; O(n log n); duration or start-time ordering fails.
Interval partitioning - answer = maximum overlap depth; min-heap of finish times.
Fractional knapsack - sort by value/weight, split the last item; optimal. 0/1 knapsack needs DP.
Huffman coding - merge two smallest frequencies; minimises Σ fᵢdᵢ; prefix-free; O(n log n).
Optimal merge/connect ropes - same as Huffman; cost = sum of internal nodes = Σ lᵢ·dᵢ.
Job sequencing with deadlines - profit-descending, latest free slot ≤ deadline; O(n log n) with DSU.
SPT minimises average completion time; EDF minimises maximum lateness.
Dijkstra and Prim/Kruskal are greedy; Dijkstra's greedy step is invalid with negative weights.
Canonical coin systems (Indian ₹1–₹500) make greedy change optimal; {1,3,4} shows it is not general.
Approximation ratios - set cover ln n, vertex cover 2, metric TSP 2 (MST doubling), LPT 4/3 − 1/3m.
Complexity - almost always sort-bound O(n log n), space O(1)–O(n); far cheaper than DP's O(nW) tables.
One counter-example disproves a greedy; no number of passing tests proves it.

Formulas and examples

Greedy correctness = greedy-choice property + optimal substructure. Both must hold; one alone is not enough.
Activity selection: pick activity i, then recurse on { j : s_j ≥ f_i }, scanning in non-decreasing f order. s = start time, f = finish time.
Fractional knapsack: maximise Σ v_i x_i subject to Σ w_i x_i ≤ W, 0 ≤ x_i ≤ 1. Greedy order: v_1/w_1 ≥ v_2/w_2 ≥ … (v = value in ₹, w = weight in kg, W = capacity in kg).
Huffman / optimal merge cost: B(T) = Σ f_i · d_i = Σ (values of all internal nodes). f_i = frequency or file length, d_i = depth = code length in bits.
Average code length L = B(T) / Σ f_i bits per symbol; space saving = (fixed-length bits − Huffman bits) / fixed-length bits.
Minimum platforms = max over time t of | { trains with arrival ≤ t ≤ departure } | (maximum interval overlap).
Mean retrieval time (tapes, SPT order l_1 ≤ l_2 ≤ … ≤ l_n): MRT = (1/n) Σ_{j=1..n} Σ_{i=1..j} l_i
Total completion time under SPT: Σ C_j = Σ_{j} (n − j + 1) p_j, with p_1 ≤ p_2 ≤ … (p = processing time).
Greedy set cover: cost_greedy ≤ H(n) × OPT, where H(n) = 1 + 1/2 + … + 1/n ≈ ln n + 0.577.

Example 1 — Activity selection (11 activities). (s, f) = (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16).

Already sorted by finish time. Take (1,4); last_end = 4.
(3,5), (0,6) rejected (3 < 4, 0 < 4). (5,7) accepted → last_end = 7.
(3,9), (5,9), (6,10) rejected. (8,11) accepted → last_end = 11.
(8,12), (2,14) rejected. (12,16) accepted.
Answer: 4 activities — (1,4), (5,7), (8,11), (12,16). Sorting by shortest duration happens to reach 4 on this instance too, but on (0,10), (9,11), (10,20) it picks (9,11) alone instead of the optimal 2.

def max_activities(acts):              # acts = [(start, finish), ...]
    acts.sort(key=lambda a: a[1])      # earliest finishing first
    chosen, last_end = [], float('-inf')
    for s, f in acts:
        if s >= last_end:              # compatible with the last pick
            chosen.append((s, f)); last_end = f
    return chosen                      # O(n log n) time, O(1) extra space

Example 2 — Fractional vs 0/1 knapsack. Capacity W = 50 kg. Items: A (₹60, 10 kg), B (₹100, 20 kg), C (₹120, 30 kg).

Ratios: A = 6, B = 5, C = 4 ₹/kg → greedy order A, B, C.
Take A whole: value ₹60, used 10 kg, left 40 kg. Take B whole: ₹100, used 30 kg, left 20 kg.
C does not fit; take 20/30 = 2/3 of it → 120 × 20/30 = ₹80.
Fractional optimum = 60 + 100 + 80 = ₹240 at exactly 50 kg.
0/1 enumeration: A+B = ₹160 (30 kg), A+C = ₹180 (40 kg), B+C = ₹220 (50 kg), A+B+C = 60 kg infeasible. 0/1 optimum = ₹220, which ratio-greedy (A then B, C rejected) would report as ₹160 — a 27% error.

	Fractional knapsack	0/1 knapsack
Items divisible	Yes	No
Method	Greedy on v/w	DP (or branch and bound)
Complexity	O(n log n)	O(nW) time, O(W) space
Example answer (W = 50)	₹240	₹220
Greedy by ratio	Optimal	Not optimal; ½-approximation only when paired with the best-single-item check

def frac_knapsack(items, W):           # items = [(value, weight)]
    items.sort(key=lambda i: i[0] / i[1], reverse=True)
    total = 0.0
    for v, w in items:
        if W >= w: total += v; W -= w
        else:      total += v * W / w; break
    return total                       # 240.0 for the data above

Example 3 — Huffman code for 100 characters. Frequencies: a 45, b 13, c 12, d 16, e 9, f 5.

Merge 5 + 9 = 14 → heap {12, 13, 14, 16, 45}
Merge 12 + 13 = 25 → {14, 16, 25, 45}
Merge 14 + 16 = 30 → {25, 30, 45}
Merge 25 + 30 = 55 → {45, 55}; Merge 45 + 55 = 100
Code lengths from the tree: a = 1, b = c = d = 3, e = f = 4 bits.
Cost = 45(1) + 13(3) + 12(3) + 16(3) + 9(4) + 5(4) = 45 + 39 + 36 + 48 + 36 + 20 = 224 bits. Cross-check = sum of internal nodes = 14 + 25 + 30 + 55 + 100 = 224. ✔
Average length = 224/100 = 2.24 bits/symbol. Fixed-length code needs ⌈log₂ 6⌉ = 3 bits → 300 bits, so the saving is 76/300 = 25.3%.

import heapq
def huffman_cost(freqs):
    h = list(freqs); heapq.heapify(h); cost = 0
    while len(h) > 1:
        a = heapq.heappop(h); b = heapq.heappop(h)
        cost += a + b                  # value of the new internal node
        heapq.heappush(h, a + b)
    return cost                        # huffman_cost([45,13,12,16,9,5]) -> 224

Example 4 — Job sequencing with deadlines. J1 (₹100, d = 2), J2 (₹19, d = 1), J3 (₹27, d = 2), J4 (₹25, d = 1), J5 (₹15, d = 3). Unit-time jobs, slots 1–3 (max deadline).

Profit-descending: J1(100, 2), J3(27, 2), J4(25, 1), J2(19, 1), J5(15, 3).
J1 → latest free slot ≤ 2 = slot 2. J3 → slot 2 busy, use slot 1. J4 → only slot 1 allowed, busy → rejected. J2 → likewise rejected. J5 → slot 3.
Schedule: slot 1 = J3, slot 2 = J1, slot 3 = J5; profit = 27 + 100 + 15 = ₹142. Taking jobs in deadline order instead would give J2/J4 in slot 1 and lose J3's ₹27 against ₹19 or ₹25.

Example 5 — Optimal merge / minimum platforms.

(a) Merge five sorted files of 20, 30, 10, 5 and 30 records. Sorted: 5, 10, 20, 30, 30. Merge 5+10 = 15 (cost 15) → {15, 20, 30, 30}; 15+20 = 35 (cost 35) → {30, 30, 35}; 30+30 = 60 (cost 60) → {35, 60}; 35+60 = 95. Total record moves = 15 + 35 + 60 + 95 = 205. Merging left to right instead (20+30, +10, +5, +30) costs 50 + 60 + 65 + 95 = 270.
(b) Trains arrive 09:00, 09:40, 09:50, 11:00, 15:00, 18:00 and depart 09:10, 12:00, 11:20, 11:30, 19:00, 20:00. Sorted arrivals 900, 940, 950, 1100, 1500, 1800; departures 910, 1120, 1130, 1200, 1900, 2000. Sweeping: +1 (1), −1 then +1 (1), +1 (2), +1 (3), then three departures before 15:00 (0 → 1), +1 (2). Minimum platforms = 3, matching the peak overlap at 11:00 (trains 2, 3, 4).

Where it is used

Networking and routing: Dijkstra/OSPF shortest-path computation in routers; greedy bandwidth and channel allocation; packet scheduling (shortest-queue, earliest-deadline) in BSNL/Jio/Airtel core-network software.
Compression and storage: Huffman tables inside JPEG, MP3, ZIP/DEFLATE, PNG and PDF — so any Indian product handling documents (DigiLocker-style archives, GST invoice storage, scanned-record systems) runs greedy codes in its libraries.
Logistics, delivery and mobility: slot and rider assignment at Swiggy, Zomato, Zepto, Blinkit and Delhivery; cab dispatch at Ola/Uber; warehouse picking routes — greedy heuristics first, optimisation later.
Scheduling and operations: IRCTC platform and rake allocation, airport gate assignment, SPT/EDF job dispatch in OS schedulers and Hadoop/Spark/Kubernetes schedulers, exam and classroom timetabling in university ERP software.
Finance and resource allocation: cash-dispensing logic in ATMs and POS change-making (greedy over RBI denominations ₹1–₹500; the ₹2000 note remains legal tender but was withdrawn from circulation in May 2023, so dispensers now use the lower set), and greedy bid/order matching in trading engines.
Job roles: SDE I/II at product companies (greedy intervals and heaps are a staple screening round), quantitative and operations-research analysts, network and firmware engineers, and competitive programming selections (ICPC, Google Kick Start style contests, GATE CS ranks).

Interview questions

Q: What two properties must a problem have for greedy to be correct? A: The greedy-choice property — some optimal solution contains the locally best first choice — and optimal substructure, so that the remaining problem can be solved independently and optimally.
Q: Why does activity selection sort by finishing time rather than starting time or duration? A: Finishing earliest leaves the maximum remaining time for all other activities; the exchange argument shows swapping any optimum's first activity for the earliest-finishing one keeps it feasible and the same size. Shortest-duration ordering fails on (0,10), (9,11), (10,20).
Q: Greedy works for fractional knapsack but not 0/1 — why? A: Fractional items let you fill the capacity exactly, so the highest ratio is always worth taking fully; with indivisible items a high-ratio item can waste capacity, and the optimum may need a combination, which only DP explores.
Q: Prove or justify that Huffman's merge of the two least-frequent symbols is safe. A: In an optimal tree the two deepest sibling leaves can be exchanged with the two lowest-frequency symbols without increasing Σ fᵢdᵢ, so there is an optimal tree in which those two are siblings — exactly what the merge assumes.
Q: Is Dijkstra's algorithm greedy, and when does it fail? A: Yes — it permanently finalises the nearest unsettled vertex. It fails with negative edge weights, because a longer-looking path can later become cheaper; use Bellman–Ford or Johnson's reweighting instead.
Q: Is greedy coin change optimal for Indian currency? A: Yes, the Indian denominations form a canonical system, so largest-first gives the fewest pieces; but it is not optimal in general — for {1, 3, 4} and amount 6 greedy uses 3 coins against the optimal 2.
Q: How do you schedule unit jobs with deadlines to maximise profit, and what is the best complexity? A: Sort by profit descending and assign each job to the latest free slot at or before its deadline; a disjoint-set structure tracking the next free slot gives O(n log n) instead of O(n²).
Q: What does the matroid theorem tell you about greedy? A: If the feasible (independent) sets are non-empty, hereditary and satisfy the exchange property, then weight-sorted greedy returns a maximum-weight independent set — which is why Kruskal's algorithm is provably optimal.
Q: Minimum number of platforms for a given set of train timings? A: Sort arrivals and departures separately and sweep with two pointers, incrementing on an arrival and decrementing on a departure; the running maximum is the answer — O(n log n), equal to the maximum interval overlap.
Q: How would you minimise average waiting time on a single server? A: Shortest-processing-time-first; by an exchange argument any adjacent pair out of order can be swapped to reduce Σ Cⱼ.
Q: Give a problem where greedy is only an approximation and state the ratio. A: Set cover — picking the set that covers the most uncovered elements costs at most H(n) ≈ ln n + 1 times the optimum; metric TSP via MST doubling is within 2×.
Q: How do you decide between greedy and DP in a 45-minute interview? A: Try to break the greedy on small inputs first; if a counter-example appears, the problem needs DP, and if none does, state the exchange argument before coding — greedy then wins on O(n log n) time and O(1) space.

Common mistakes

Assuming instead of proving. Writing "greedy clearly works" with no exchange argument loses most of the marks in a university or GATE-style proof question, and fails the interview follow-up.
Applying the ratio rule to 0/1 knapsack (or the greedy coin rule to arbitrary denominations) and reporting the sub-optimal value as the answer.
Sorting by the wrong key — start time or duration in activity selection, deadline instead of profit in job sequencing, or forgetting reverse=True on the value/weight ratio.
Mishandling boundary and tie cases — treating intervals that merely touch (s == previous f) as overlapping, or using strict instead of non-strict comparisons, which changes the count by one.
Forgetting to re-heapify / re-insert the merged node in Huffman and optimal-merge code, which produces a wrong tree cost; and computing cost from code lengths without cross-checking against the sum of internal nodes.
Quoting Dijkstra as a general shortest-path algorithm and using it on graphs with negative edges or on problems with a second constraint (e.g. at most k stops).
Ignoring the cost of the sort when stating complexity (calling a greedy solution O(n) when it sorts), or using floating-point ratios where cross-multiplication of integers avoids precision ties.