Greedy
This page briefly introduces greedy algorithms.
Introduction
A greedy algorithm has the computer simulate the way a greedy person makes decisions. This person is extremely greedy: at every step they take the action that is best by some measure. They are also short-sighted: they only ever look at what is in front of them and never consider what consequences a choice may have later.
As you would expect, the greedy method does not always find an optimal solution, so whenever you use it, make sure you can prove that it is correct.
Explanation
When it applies
Greedy algorithms work especially well on problems with optimal substructure. Optimal substructure means that the problem can be solved by breaking it into subproblems, and that optimal solutions to the subproblems carry forward to an optimal solution to the final problem.1
Proof
Common proof techniques include the exchange argument and mathematical induction; the two can also be combined.
- Exchange argument: start from an arbitrary optimal solution and turn it into the solution found by the greedy algorithm through finitely many exchanges or replacements, each of which preserves feasibility and does not make the objective value worse. This proves that the greedy solution is optimal as well. The proof is often written as a proof by contradiction.
- Induction: first compute the optimal solution \(F_1\) for the base case (for example \(n = 1\)), then prove that for every \(n\), \(F_{n+1}\) can be derived from \(F_{n}\).
Key points
Common problem types
In problems up to the difficulty of the Senior division, two kinds of greedy algorithm are the most common.
- Sort XXX in some order, then choose in some order (for example, from smallest to largest).
- Repeatedly take the largest/smallest thing in XXX and update XXX. (Taking the maximum/minimum can sometimes be optimized, for example by maintaining it with a priority queue.)
The difference is that the first kind is always offline: you can process everything first and choose afterwards. The second kind may be online, so you have to choose as you process.
Greedy by sorting
The sorting method, or adjacent exchange method, typically applies when the input is an array whose elements carry a few weights each (usually one or two): sort the array, then traverse it and simulate the computation to find the optimal value.
Example: NOIP 2012 King's Game
It is the national day of country H, and the king has invited \(n\) ministers to play a game with prizes. First, he has every minister write an integer on his left hand and another on his right hand, and the king writes an integer on each of his own hands as well. Then the \(n\) ministers line up, with the king at the very front of the line. Once they are lined up, every minister receives some gold coins from the king: the number of coins a minister receives is the product of the numbers on the left hands of everyone in front of him, divided by the number on his own right hand, rounded down.
The king does not want any one minister to receive an especially large reward, so he asks you to rearrange the line so that the minister who receives the most receives as little as possible. Note that the king always stays at the very front of the line.
Approach
Let \(a_i\) and \(b_i\) be the numbers on the left and right hands of the \(i\)-th minister in the current permutation. We derive the greedy strategy by the adjacent exchange method.
Ignore the floor for now, and let \(s\) be the product of the \(a_i\) of everyone in front of the \(i\)-th minister. Before the swap, the larger of the two ministers' rewards is
After the swap, the larger of the two is
If \(a_i b_i\le a_{i+1}b_{i+1}\), then since \(b_{i+1}\le a_{i+1}b_{i+1}\), expression \((1)\) is no greater than expression \((2)\). The floor function is monotone and \(\max(\lfloor u\rfloor,\lfloor v\rfloor)=\lfloor\max(u,v)\rfloor\), so swapping the two ministers does not make the largest reward smaller. Sorting by \(a_i b_i\) in ascending order is therefore optimal.
In the implementation, we store the two input numbers in a struct and overload an operator:
1 2 3 4 5 | |
Greedy with undo
The idea is to accept each new option provisionally; if a constraint is then violated, undo the option in the chosen set that is worst by the greedy criterion. The strategy still needs a proof of correctness.
Example: [USACO09OPEN] Work Scheduling
John's working day starts at time \(0\) and has \(10^9\) units of time. In any unit of time he may pick any one of \(N(1 \leq N \leq 10^5)\) jobs, numbered \(1\) to \(N\), and complete it. Job \(i\) has deadline \(D_i(1 \leq D_i \leq 10^9)\) and brings a profit of \(P_i( 1\leq P_i\leq 10^9 )\) once completed. Given the profits and deadlines of the jobs, find the maximum profit John can obtain.
Approach
- First assume that every job gets done: sort the jobs by deadline and push them into the queue in that order.
- When deciding whether to do job
i, if its deadline meets the condition, compare the job with the lowest-paying element in the queue. If jobipays more, we undo the earlier choice:ans += a[i].p - q.top().
A priority queue (a min-heap) keeps the smallest element at the front of the queue. - The condition
a[i].d<=q.size()can be read as follows: onlya[i].djobs fit into the period from 0 toa[i].d, andq.size()>=a[i].dmeans that completingq.size()jobs takes at leasta[i].dtime. So when jobiis the more profitable one, the least profitable job should be swapped out of the priority queue.
Reference code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
Complexity analysis
- Space complexity: with \(n\) jobs in the input, the array \(a\) uses \(n\) elements, and in the worst case the priority queue stores \(n\) elements, so the space used is \(O(n)\).
- Time complexity:
std::sorttakes \(O(n\log n)\) and maintaining the priority queue takes \(O(n\log n)\), so the algorithm runs in \(O(n\log n)\) overall.
Difference from dynamic programming
An ordinary greedy algorithm relies on local choices that can be proved safe; dynamic programming instead maintains the optimal value of every state and compares the candidate transitions.
Practice problems
References and notes
-
Greedy algorithm - Wikipedia, the free encyclopedia (in Chinese) ↩
This page is an unofficial English translation of the original OI Wiki page (revision 9bb3a8e6), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, HeRaNO, Planet6174, niltok, Xeonacid, 24OI-bot, FTYC919, abc1763613206, hsfzLZH1, Chrogeek, zirnc, Marcythm, ouuan, H-J-Granger, Henry-ZHR, Makkiy, NachtgeistW, StudyingFather, leoleoasd, sshwy, Enter-tainer, tinjyu, ksyx, RoxasKing, kenlig, iamtwz, qiqistyle, Great-designer, Tiphereth-A, LeiJinpeng, shawlleyw, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.