Greedy Algorithms

DSA · Algorithm Techniques

Theory

A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, without revisiting earlier decisions. It is fast and simple, but it only gives the optimal answer when the problem has the greedy-choice property, which you should justify (often by an exchange argument). Activity selection, Huffman coding, Dijkstra and Kruskal are greedy; coin change with arbitrary coins is a classic case where greedy fails.

Why we use it

When it works, greedy is usually the simplest and fastest correct solution, often O(n log n) due to sorting.

When to use it

Use greedy for interval scheduling, minimum platforms, fractional knapsack, Huffman coding and MSTs. Verify with a counterexample check before trusting it.

How it works

  1. Sort or order the choices
  2. Take the best-looking choice now
  3. Choice is valid? Yes: Add to solution. No: Skip it.
  4. More choices? Yes: Repeat. No: Done.
  5. Works only when local best leads to global best

Syntax

sort items by the key that makes the local choice safe
for item in items:
    if item fits with choices so far: take it

Typical time: O(n log n)

Example

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]

def max_meetings(meetings):
    chosen, last_end = [], -1
    for start, end in sorted(meetings, key=lambda m: m[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

print("Meetings booked:", max_meetings(meetings))

def greedy_coins(amount, coins):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c; used.append(c)
    return used

print("Indian coins for 289:", greedy_coins(289, [1, 2, 5, 10, 20, 50, 100, 200]))
print("Greedy fails for 6 with [1,3,4]:", greedy_coins(6, [1, 3, 4]), "(best is [3, 3])")

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic