Greedy

How do I know a greedy algorithm is correct?

You argue it, because testing a few inputs proves nothing. The standard move is the exchange argument: take any optimal answer that differs from the greedy one, look at the first place they differ, and swap the greedy choice in. If the result is still valid and still just as good, greedy is safe. The second move is "greedy stays ahead": show that after every step the greedy partial answer is at least as far along, by whatever measure the problem scores, as any other partial answer. If neither argument goes through, that is real evidence the greedy is wrong, not a gap in your writing.

What is an exchange argument?

Suppose an optimal answer O disagrees with the greedy answer G at the first choice. Replace that one choice in O with the greedy choice. Show two things: the result is still a legal answer, and it is no worse than O. Now O and G agree one step further along. Repeat, and you turn O into G without ever losing quality, so G is optimal too. For interval scheduling the swap works because the greedy choice ends earliest, so it frees at least as much of the line as the choice it replaces.

When does greedy fail and I need dynamic programming?

When taking the locally best option can rule out a better plan later. Coin change with coins 1, 3 and 4 is the standard example: paying 6 by taking the 4 first needs three coins, while two 3s need two. The exchange argument fails there because swapping a 4 into an optimal answer can force two extra 1s. Once you cannot make the swap argument, try every choice and cache the results, which is DP.

Why sort by end time for interval scheduling, and not by start time?

Because the only thing a chosen interval costs you is the part of the line it occupies after it starts, and the interval that ends earliest occupies the least of what is still to come. Sorting by start can take one long interval that blocks several short ones. Sorting by duration fails too: a short interval sitting across the middle can collide with two intervals that would have fitted either side of it. Section 07 of this page runs all three keys on the same four intervals and records what each one keeps.

Is a greedy solution always faster than DP?

Usually, and by enough to matter. Greedy is a sort plus one pass, so O(n log n), or O(n) when the order is already given. A DP over the same choices fills a table and costs at least O(n) states times the work per state, often O(n times target). But speed is not the reason to choose greedy. Correctness is: use greedy when you can make the argument, and DP when you cannot.