Greedy Algorithms
Greedy algorithms: the locally best step, the non-overlapping intervals problem, limits of applicability.
A greedy algorithm makes the locally best choice at every step and never reconsiders. When greed is correct, you get the fastest and shortest solution possible. When it is not, it confidently outputs a wrong answer. The whole art is telling one from the other.
The benchmark problem: given n events with start and end times, pick the maximum number of non-overlapping ones. The correct greedy: always take the event with the EARLIEST END — it leaves the most time for the rest.
Maximum non-overlapping intervals. Enter: 4, then "start end" pairs: 1 3, 2 5, 4 7, 6 8
Why "earliest end" is correct: suppose the optimal answer took some other event first. Replace it with the earliest-ending event — it finishes no later, so the rest of the schedule stays valid. The answer did not get worse. This proof pattern (the "exchange argument") is the standard for greedy algorithms.
And here is a counterexample showing greed is not universal: coins of denominations 1, 3 and 4, make 6. The greedy takes 4+1+1 — three coins. The optimum: 3+3 — two. Coin systems like this need dynamic programming (next level!), not greed.
Signs that greedy MIGHT work: sorting obviously suggests itself; the current choice doesn't constrain the future more than any other; you can sketch an exchange argument.
Task: start simple: given the lengths of n ropes, joining two ropes costs the sum of their lengths; prove (or refute on a small test) that greedily joining the two shortest gives the minimum cost. Check yourself by brute force for n = 4.
Mark the lesson as completed and move on to DSU.