Released · improving
Algorithm
Greedy algorithms take the locally best choice at each step and never look back, solving interval scheduling, Huffman coding and fractional knapsack fast.
A greedy algorithm builds its answer through a series of choices: at each step it takes the candidate that looks best by a fixed rule and never revisits that decision. Most greedy algorithms sort the candidates or put them in a priority queue and accept them one at a time, so the code is short and the running time is usually O(n log n), dominated by sorting or heap operations.
When greedy works it is the fastest and simplest solution, but it does not always work. An optimal result requires the greedy choice property and optimal substructure, usually proven with an exchange argument. A single counterexample, such as making 6 from coins of 1, 3 and 4, means you need dynamic programming instead. The greedy principle also sits at the heart of widely used algorithms such as Huffman coding, Dijkstra's shortest paths and minimum spanning trees.
Start with interval scheduling (activity selection) and use an exchange argument to explain why picking the meeting that ends first is correct. Then implement Huffman coding, the fractional knapsack and meeting-room allocation with a heap, and make a habit of comparing greedy answers with brute force on small inputs; it is the fastest way to catch a wrong rule in a coding interview.
Some optimal solution must contain the first greedy choice; this is the key condition for a greedy algorithm to be correct.
Show that swapping elements of any optimal solution toward the greedy one never makes it worse, which proves the rule is safe.
Candidates are ranked by end time, value per weight or frequency, or pulled from a heap, so most greedy algorithms run in O(n log n).
For arbitrary coin systems or the 0/1 knapsack the greedy rule gives wrong answers, and dynamic programming takes over.
This program picks the largest set of non-overlapping meetings. It sorts the meetings by end time and accepts one only if it starts after the last chosen meeting ends. Sorting costs O(n log n) and the scan O(n); in the example, 4 of the 11 meetings are chosen.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySix chapters that take you from installation to the core ideas of Greedy algorithms.
Ask questions, share experience and trade opinions about Greedy algorithms.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.