Make locally optimal choices that lead to a globally optimal solution.
Greedy algorithms make the locally best choice at each step. They work when the problem has the greedy choice property and optimal substructure.
Usually O(n log n) for sorting + O(n) for sweep
O(1) typically
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
local optimum leads to global optimum
sort intervals, tasks, or items before making decisions
sort by end time for max non-overlapping intervals
track the farthest reachable index
use greedy when provably correct; use DP otherwise
proof technique: show swapping improves or maintains solution