Greedy choices

A greedy algorithm makes the choice that looks best right now and does not take it back. It is fast when that local choice is safe. It is wrong when waiting would have opened a better path later. The skill is telling those problems apart, not applying "sort and scan" to everything you see.

Interval scheduling is a case where greedy is safe. You want as many half-open intervals as possible with no pair overlapping. Sort by finishing time, earliest first. Take the first interval, then the next one that starts at or after that finish. Taking the interval that frees you soonest leaves the most room afterwards, and for this problem that local rule matches the best possible count. Touching endpoints is allowed when the intervals are half-open: one ends where the next starts.

Sorting by start time instead can fail. An early interval that runs for a long time blocks several short ones that would have fit. Same data, worse rule. When you invent a greedy rule, try to name a case it gets wrong. If you cannot, you might be done. If you can, it is not the rule.