AI Glossary / Data science and analytics / Intermediate
Greedy algorithms
Definition
Greedy algorithms build a solution by repeatedly choosing the option that looks best according to a specified local rule. Once a choice is made, a basic greedy algorithm usually commits to it rather than exploring every alternative combination. Some greedy algorithms are provably optimal for particular problems. Others are useful heuristics that can return a feasible but suboptimal answer.
What it means
The word greedy describes a decision process, not a moral judgment. The algorithm has a rule such as selecting the earliest-finishing compatible appointment or taking the largest coin that does not exceed the remaining amount. The important question is whether that rule leads to the best complete solution for the precise problem. A sensible immediate choice can consume a resource or block a combination that would have produced a better final result.
How it works
Define the objective, the available choices, and the constraints. At each step, rank or evaluate the choices using the greedy criterion, select an admissible option, and update what remains possible. Continue until the stopping condition is met. To claim optimality, the rule needs a valid argument under the stated assumptions, often showing that an optimal solution can be changed to include the greedy choice without becoming worse. If no such guarantee is established, compare results with exact solutions on small cases or useful bounds and alternatives on larger cases.
Three practical examples
- Appointment selection: for the standard problem of maximizing the number of non-overlapping fixed intervals on one resource, repeatedly choosing the earliest-finishing compatible interval gives an optimal count.
- Change making: repeatedly taking the largest affordable denomination is a simple rule, but its optimality depends on the available denominations and assumptions.
- Resource planning: a team may use a greedy priority rule to construct a quick candidate allocation, then assess feasibility and solution quality before using it operationally.
Think of it this way
Think of filling a bag by choosing the most appealing available item at each step. The process is easy to follow, but an attractive large item might leave no room for a better combination of smaller items. This analogy illustrates local choice and commitment; it does not establish that all packing problems or greedy rules behave alike.
Worked example
Suppose unlimited coins are available in denominations 1, 3, and 4, and the goal is to make a total of 6 using the fewest coins. The largest-coin-first rule chooses 4, leaving 2. It then chooses 1, leaving 1, and another 1. The result is three coins: 4 + 1 + 1.
The alternative 3 + 3 uses only two coins. One coin cannot make 6 because there is no denomination 6, so two is optimal in this example. The greedy method finds a valid solution but misses the minimum coin count. The failure is not an implementation bug; the local rule lacks the required guarantee for this denomination system. If the goal, denominations, or availability constraints change, the analysis must be repeated. A rule that works for a familiar currency cannot automatically be transferred to an arbitrary collection of package sizes or payment units.
Illustrative case study
In a fictional booking system, developers select compatible requests by earliest finish time and correctly maximize the number of accepted fixed appointments on one room. Later, the business introduces different revenues for different requests and changes the goal to maximizing revenue. The same algorithm can still produce a conflict-free schedule, but its earlier optimality guarantee no longer answers the new question. The team tests weighted cases and evaluates a method designed for the revised objective. The case shows why a business-rule change can invalidate an algorithm's guarantee even when the software still runs.
Common misconceptions and mistakes
Greedy does not mean random, and it does not always mean approximate. Some greedy methods have exact guarantees under their assumptions. Conversely, passing several examples is not a proof of optimality. Choosing the earliest-starting or shortest appointment is not interchangeable with choosing the earliest-finishing appointment in the standard interval-selection problem. A feasible result merely satisfies constraints; an optimal result also meets the objective as well as any feasible alternative. Tie-breaking, missing constraints, and changing objectives deserve explicit attention.
Business use
A greedy method can be useful when a fast, understandable decision rule is valuable. Specify what it optimizes and whether that claim is proven, bounded, or only supported by experiments. Compare the cost of a less-than-best decision with the time and resources required for a more elaborate method. Keep representative failure cases in evaluation, especially cases involving interacting constraints. For a live workflow, monitor both feasibility and the business outcome, because an unchanged rule can become inappropriate when capacity, priorities, or customer requirements change.
People also ask
Are greedy algorithms always optimal?
No. Optimality depends on the problem, rule, and assumptions.
Are they always wrong for difficult problems?
No. They can provide useful solutions, and some have formal approximation guarantees.
Does a greedy algorithm learn from data?
Not necessarily. It is an algorithmic strategy; its scoring rule may be fixed or may use learned estimates.
Check your understanding
Why does largest-coin-first fail for total 6 with denominations 1, 3, and 4?
Answer: Taking 4 commits the algorithm to two additional 1 coins, while taking two 3 coins uses fewer coins overall. The best-looking first step does not preserve an optimal complete solution.
Related terms
- Optimization
- Heuristic
- Optimal solution
- Dynamic programming
- feasible solution
- approximation algorithm
- interval scheduling
- greedy choice property
Learn next
Trace several small problems by hand and compare each greedy result with all feasible alternatives. Then study the exchange argument for earliest-finish-time interval selection. Compare greedy choice with dynamic programming, which can retain information about alternative subproblems rather than committing to one immediate choice.
More in Data science and analytics
- Gated recurrent unit - A gated recurrent unit, usually shortened to GRU, is a neural-network component for processing ordered sequences.
- Geospatial analytics - Geospatial analytics is the analysis of data that have a geographic location or spatial relationship.
- Goodness-of-fit - Goodness of fit describes how well a statistical model agrees with the data being examined.
- Harking - HARKing means hypothesizing after the results are known and presenting the resulting hypothesis as though it had been proposed before examining those results.
- Heatmap - A heatmap is a visualization that represents numerical values using color.
- Histogram - A histogram displays the distribution of numerical observations by dividing their range into intervals, called bins, and drawing a bar for each interval.
Sources
Kevin Wayne, Princeton course materials on greedy algorithms and interval scheduling: https://www.cs.princeton.edu/~wayne/cs423/lectures/greed-4up.pdf Princeton, interval-selection rule and analysis: https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/04GreedyAlgorithmsI-2x2.pdf Original research on canonical coin systems: https://arxiv.org/abs/0809.0400
Previous: Greedy agent Next: Greedy best-first search