Sort, then take greedily

30 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four people weigh 3, 2, 2, 1. A boat carries at most two people and at most 3 units of weight. What is the fewest boats?

By hand you would try pairings. 3 cannot share with anyone, since 3 + 1 = 4 is too much. The 1 can share with a 2. So: {3}, {2, 1}, {2}, three boats. For four people you can try all pairings. For 50,000 people the number of ways to pair them is astronomical, and even "try pairing each person with each other" is 50,000 × 50,000 = 2.5 billion checks.

Build the structure, one piece at a time

Two pieces. First, sort the weights: [1, 2, 2, 3]. Second, two pointers, one at the lightest person and one at the heaviest. At each step the heaviest person definitely needs a boat now (nobody later is heavier). The only question is whether someone can ride along, and the best candidate is the lightest person, because if anyone fits with the heaviest, the lightest does.

1. Pointers at 1 and 3. 1 + 3 = 4 is over 3. The 3 goes alone. One boat, heavy pointer moves to the 2.
2. Pointers at 1 and 2. 1 + 2 = 3 fits. They share. Two boats, both pointers move inward.
3. One person left, a 2. Alone. Three boats.

The "structure" is the sorted order itself: once sorted, the questions "who is heaviest" and "who is lightest" are answered by position, with no searching.

Why it is correct

This is a greedy choice, and greedy choices need a proof, called an exchange argument: take any optimal plan and show you can swap it, without making it worse, into the plan the greedy rule makes. Here the rule is "pair the heaviest, H, with the lightest, L, if they fit". Suppose an optimal plan has H alone and L with someone else, X. Move L into H's boat (they fit by assumption) and leave X alone: still a valid plan with the same number of boats. Suppose instead H rides with some Y and L with X. Swap L and Y: H + L ≤ H + Y fits, and X + Y ≤ X + H fits (since Y ≤ H). Same number of boats. So some optimal plan agrees with the greedy first step, and repeating the argument on the remaining people shows the greedy plan is optimal.

if L + H ≤ limit and Y ≤ H, then X + Y ≤ X + H: the swap never breaks a boat

Why it is fast

Sorting n weights takes O(n log n). The two-pointer sweep moves each pointer at most n times in total, so it is O(n). For 50,000 people that is about 800,000 steps for the sort and 50,000 for the sweep, against 2.5 billion pair checks. The sort is the price of being able to answer "heaviest" and "lightest" instantly.

How to recognise it in an interview

Cues: a capacity or limit, "minimum number of groups or boats or trucks", "maximum number you can satisfy", choices that feel like they should be made largest-first or smallest-first. Say: I will sort, make the obvious local choice, and justify it with an exchange argument. Then actually give the two-line argument; interviewers listen for it. Boats to Save People is the example. Assign Cookies sorts children and cookies and gives each child the smallest cookie that satisfies them. Two City Scheduling sorts by the cost difference between the two cities, and the exchange argument is the same shape.

02The idea in one line

Order by the key that an exchange argument proves safe, then commit one by one.

Reach for it when: Assign cookies, boats to save people, two city scheduling, minimum cost to hire.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Boats to Save People [3,2,2,1] limit 3. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort first; pair the heaviest person with the lightest if they fit
2. Exchange argument: if the heaviest can share, sharing with the lightest never hurts
3. 3 goes alone (too heavy to share)
4. 1 + 2 = 3 ≤ 3: they share a boat
5. 2 goes alone (last person)
6. Pointers crossed: 3 boats
7. Sort O(n log n), then one two-pointer sweep

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Reset-on-negative sweep, Last-occurrence partition, Two-pass neighbour constraints, Counting-based greedy (small alphabet), Two-pointer assignment after sorting.