Is the Greedy — locally optimal, globally lucky lesson free?

Yes. The first 5 lessons on PyRun are free forever — no signup, no card. Greedy — locally optimal, globally lucky runs real Python in your browser via Pyodide.

How long does the Greedy — locally optimal, globally lucky lesson take?

About 12 minutes end-to-end. It's a hands-on lesson — you read a paragraph, edit the code, and run it in the same tab.

Do I need to install Python to try the Greedy — locally optimal, globally lucky lesson?

No install required. PyRun runs real CPython in your browser via Pyodide (Python compiled to WebAssembly). Works on Chrome, Firefox, Safari, and Edge — desktop or mobile.

What level is the Greedy — locally optimal, globally lucky lesson?

Advanced level. Assumes comfort with classes, functions, and standard library. Not for first-time Python learners.

← All lessons

Advanced·12 min·dsa · greedy · interview

Greedy — locally optimal, globally lucky

Greedy algorithms

A greedy algorithm builds the answer one step at a time, committing to whatever looks best right now. When it works, fastest thing you can write. When it doesn't, silently returns wrong answers.

When greedy is safe

Exchange argument. Swap one choice in an optimal solution for the greedy one. If still optimal, greedy is safe by induction.
Matroid intuition. MST is the textbook example.

Three patterns

Activity selection. Sort by finish time, pick earliest-ending that doesn't overlap. Sorting by start or duration fails.

Coin change canonical. Indian/US coins are canonical (greedy works). (1, 3, 4) making 6: greedy gives 4+1+1, optimal is 3+3. When denominations look odd, use DP.

Jump game. Walk left to right, keep reach = max(reach, i + nums[i]). If i > reach, stuck.

Common pitfalls

Sort key by feel. Activity selection by shortest interval is wrong. Justify sort with exchange argument.
Assuming coin systems are canonical. Interview variants deliberately break this.
Greedy on graphs. Dijkstra works for non-negative weights only. Negative → Bellman-Ford.

When to skip greedy

Overlapping subproblems → DP. Combinatorial pruning → backtracking. Greedy is right only when a proof (even hand-wavy) says local implies global.

Try it

Modify activity_selection to also return count of meetings skipped.
Write min_jumps(nums) — fewest jumps to reach end. Greedy on furthest-reach frontier.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write greedy_coins(amount) that returns the minimum number of Indian rupee coins needed to make amount using denominations [500, 200, 100, 50, 20, 10, 5, 2, 1]. Use the greedy approach (largest coin first).
Exercise 2
Write min_meeting_rooms(intervals) where intervals is a list of [start, end] pairs. Return the minimum number of rooms needed so no two overlapping meetings share a room.
Exercise 3
Write max_activities(activities) where each activity is a [start, end] pair. Return the maximum number of non-overlapping activities you can attend (classic activity selection — greedy by earliest end time).

← PreviousBacktracking — try, recurse, un-try Next →Bit manipulation — arithmetic in binary

Greedy — locally optimal, globally lucky

Greedy algorithms

A greedy algorithm builds the answer one step at a time, committing to whatever looks best right now. When it works, fastest thing you can write. When it doesn't, silently returns wrong answers.

When greedy is safe

Exchange argument. Swap one choice in an optimal solution for the greedy one. If still optimal, greedy is safe by induction.
Matroid intuition. MST is the textbook example.

Three patterns

Activity selection. Sort by finish time, pick earliest-ending that doesn't overlap. Sorting by start or duration fails.

Coin change canonical. Indian/US coins are canonical (greedy works). (1, 3, 4) making 6: greedy gives 4+1+1, optimal is 3+3. When denominations look odd, use DP.

Jump game. Walk left to right, keep reach = max(reach, i + nums[i]). If i > reach, stuck.

Common pitfalls

Sort key by feel. Activity selection by shortest interval is wrong. Justify sort with exchange argument.
Assuming coin systems are canonical. Interview variants deliberately break this.
Greedy on graphs. Dijkstra works for non-negative weights only. Negative → Bellman-Ford.

When to skip greedy

Overlapping subproblems → DP. Combinatorial pruning → backtracking. Greedy is right only when a proof (even hand-wavy) says local implies global.

Try it

Modify activity_selection to also return count of meetings skipped.
Write min_jumps(nums) — fewest jumps to reach end. Greedy on furthest-reach frontier.

Practice

3 graded exercises

Write the code, click Check. We’ll tell you exactly what to fix.

Progress0 / 3

Exercise 1
Write greedy_coins(amount) that returns the minimum number of Indian rupee coins needed to make amount using denominations [500, 200, 100, 50, 20, 10, 5, 2, 1]. Use the greedy approach (largest coin first).
Exercise 2
Write min_meeting_rooms(intervals) where intervals is a list of [start, end] pairs. Return the minimum number of rooms needed so no two overlapping meetings share a room.
Exercise 3
Write max_activities(activities) where each activity is a [start, end] pair. Return the maximum number of non-overlapping activities you can attend (classic activity selection — greedy by earliest end time).