Greedy Algorithms
Software Engineer path · lesson 32 of 99Solve scheduling and optimization problems by always making the locally optimal choice. Learn the Activity Selection Problem — the canonical greedy success — and the exchange argument that proves it optimal.
Times 0–24, like 1-4, 3-5. Up to 12.
Only earliest end is always optimal; the presets show the others failing.
Sort by end time: [1,4] [3,5] [0,6] [5,7] [3,9] [5,9] [6,10] [8,11] [8,12] [2,14] [12,16].
- 1sort activities by end time
- 2lastEnd = -∞
- 3for a in activities:
- 4 if a.start >= lastEnd: choose a; lastEnd = a.end # finishes earliest
- 5 else: skip a — it overlaps the last choice
- Checks
- 0 / 11
- Chosen
- 0 / 4
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Does greedy work here?
Sort each problem by whether the obvious greedy choice is optimal.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Greedy is optimal
Drop items hereGreedy can fail
Drop items hereTest your knowledge
What is the time complexity of the greedy Activity Selection algorithm?
Write the code
Activity Selection — Maximum Non-Overlapping Count
def activity_selection(activities: list[list[int]]) -> int:
"""
Return the maximum number of non-overlapping activities.
activities: List of [start, end] pairs.
"""
# Your code here
passThe short version
You manage a single conference room. A naive scheduler picks meetings by importance or length. A greedy scheduler always picks whichever meeting ends soonest — leaving the room free for as many future bookings as possible. Counterintuitively, this "earliest finisher first" rule — with zero lookahead — is provably optimal via an exchange argument: swapping any other first pick for the earliest-ending one never reduces the total count.
In more depth
Greedy algorithms build a solution incrementally, always taking the locally optimal option without revisiting previous choices. The decisive question is: does the greedy choice property hold? — meaning a globally optimal solution always includes the greedy first choice.
Activity Selection is the canonical greedy success. After sorting by end time, the algorithm scans left-to-right and selects each activity whose start time >= lastEnd. The proof is an exchange argument: suppose an optimal solution starts with activity B instead of the earliest-finishing A. Since end(A) <= end(B), replacing B with A produces a solution that is still valid and has the same count — so including A is never worse. By induction, the greedy solution is globally optimal.
The same "sort by end" key powers related problems: Interval Scheduling Maximization (maximize tasks on one machine), and LeetCode 435 Non-overlapping Intervals (minimum removals = total − greedy count). Interval Partitioning (minimize conference rooms) instead uses a min-heap keyed on room end times.
Other greedy classics include Fractional Knapsack (sort by value/weight ratio; indivisible items break this), Huffman Coding (always merge two lowest-frequency nodes), Dijkstra's shortest path (relax the closest unvisited vertex), and Kruskal's MST (add the cheapest edge that doesn't form a cycle).
Greedy fails when local choices foreclose globally better branches — 0/1 Knapsack and shortest path with negative edges need DP or more careful relaxation.
When to reach for this
- Select maximum items from a set of overlapping intervals
- "Schedule as many as possible" or "finish earliest first" phrasing
- Minimize number of resources (rooms, machines) to serve all requests
- Fractional resource allocation where items are divisible
- Exchange argument holds: swapping the greedy first choice never worsens the solution
- Keywords: interval scheduling, activity selection, greedy choice property, non-overlapping
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required