DSA Notes

Techniques

Greedy

Take the choice that looks best now, and prove it is never wrong.

The idea

A greedy algorithm builds the solution step by step and never revisits a choice. It is fast and short, but only correct when the local choice can be shown to be safe.

The standard proof is an exchange argument: take any optimal solution, swap in the greedy choice, and show the result is no worse.

Most greedy solutions start by sorting, and the key you sort by is the whole idea. If you cannot prove the choice, look for a small counter-example; if you find one, the problem probably needs dynamic programming.

Sample problem

881. Boats to Save People ↗ Medium

Each boat carries at most two people and at most `limit` weight. Return the minimum number of boats needed to carry everyone.

people = [1,2,4,5,3], limit = 6
output = 3   (5+1, 4+2, 3)

Why the solution works

The heaviest person must go in some boat. The greedy choice: pair them with the lightest person if that fits, otherwise send them alone.

Why it is safe (exchange argument): if the heaviest can share with anyone, they can share with the lightest. Take an optimal plan where the heaviest shares with someone else and swap that partner with the lightest person; every boat is still within the limit, and the number of boats is unchanged.

After sorting, two pointers apply the choice repeatedly from both ends.

Complexity: O(n log n) time for the sort, O(1) extra memory.

Watch out

  • Plausible is not proven: test the idea against a brute force on small inputs.
  • The sort key matters. For choosing the most non-overlapping intervals, sort by end time, not start time.
  • Decide how ties are broken; a wrong tie rule can break an otherwise correct greedy.
Watch it run

Try your own input

Practise on LeetCode