12. Greedy

Greedy means taking the choice that looks most profitable right now, and never going back. The algorithm is usually short and fast — often just a sort followed by a single pass. That is also where the danger lies: a wrong greedy looks just as convincing as a correct one.

General form

1. Sort the data by some measure.
2. Go through it once from the front.
3. At each step, take the item if possible.

The number of steps is O(n log n) because of the sort, so greedy suits problems with constraints of n ≤ 200,000 or more.

All of the difficulty of greedy is in step 1: sorted by what?

Sorting measures that are often tried, and the kind of problem each one usually fits:

This list is a list of guesses, not a list of answers. Every guess must still be tested, and the last part of this chapter covers how.

An example that works: making change

Given the Indonesian currency denominations 100,000, 50,000, 20,000, 10,000, 5,000, 2,000, and 1,000. What is the fewest number of notes needed to pay k rupiah?

Greedy: take as many as possible of the largest denomination, then move down.

int pecahan[] = {100000, 50000, 20000, 10000, 5000, 2000, 1000};

int lembar = 0;
for (int i = 0; i < 7; i++) {
    lembar += k / pecahan[i];
    k %= pecahan[i];
}

For k = 87,000: 87,000 → one 50,000, remaining 37,000 → one 20,000, remaining 17,000 → one 10,000, remaining 7,000 → one 5,000, remaining 2,000 → one 2,000. Five notes, and there is no way to do it with four.

Why greedy is correct here: every Indonesian denomination is always divisible by, or "close enough" to, the denomination below it, so taking one large note can never be beaten by several small notes. That property belongs to the list of denominations, not to the problem "find the fewest notes" — and that is what makes the next example fail.

An example that fails: made-up denominations

Change the denominations to 1, 3, and 4, then pay 6.

• Greedy: take 4, remaining 2; take 1, remaining 1; take 1. Three coins.
• Best answer: 3 + 3. Two coins.

Greedy is wrong. Nothing can fix it by adding a small rule; a problem like this needs dynamic programming (Chapter 13).

If all values from 1 to 10 are checked, the failures turn out to be rare — and that is exactly the danger:

Eight out of ten values match. If you only try k = 1 to k = 5, greedy looks perfectly correct. This is why greedy must not be "tested at a glance": what is needed is an exhaustive check over small data, not two or three examples that happen to come to mind.

A classic example: activity scheduling

There are n activities, each with a start time s[i] and a finish time f[i]. You can only attend one activity at a time. What is the largest number of activities you can attend?

Three sorting measures that look reasonable:

The correct reason: the activity that finishes earliest leaves the most time for the following activities. Any other solution can have its first activity swapped for the earliest-finishing activity without making the answer worse.

Both wrong measures have very small counterexamples:

• Earliest start time. Activities (0–10), (1–2), (3–4). Greedy takes (0–10) and stops there: 1 activity. Best answer (1–2) and (3–4): 2 activities.
• Shortest duration. Activities (1–5), (4–6), (5–9). Greedy takes (4–6), which has duration 2, and the other two now clash with it: 1 activity. Best answer (1–5) and (5–9): 2 activities.

Tracing the correct greedy on six activities (1–4), (3–5), (0–6), (5–7), (3–8), (8–10) — already sorted by finish time:

The answer is 3 activities. Look at activity 3, the longest one (0–6): even though it starts earliest, taking it would actually block two other activities.

sort(keg, keg + n, [](Kegiatan a, Kegiatan b) {
    return a.selesai < b.selesai;
});

int banyak = 0;
int waktu = -1000000000;          // when the last activity finished
for (int i = 0; i < n; i++) {
    if (keg[i].mulai >= waktu) {
        banyak++;
        waktu = keg[i].selesai;
    }
}

The form [](...) { return ...; } is a lambda: a small unnamed function passed to sort as the sorting rule. For this book it is enough to recognize the pattern — return true if a must come before b.

struct Kegiatan {
    int mulai, selesai;
};
Kegiatan keg[100005];

Example: boat loading

n people are waiting to cross. The weight of person i is b[i]. Each boat carries at most two people and a total weight of at most k. What is the fewest number of boats?

The correct greedy: sort the weights, then pair the lightest with the heaviest. If both fit, send them together; if not, the heaviest goes alone.

sort(b, b + n);

int kiri = 0, kanan = n - 1, perahu = 0;
while (kiri <= kanan) {
    if (b[kiri] + b[kanan] <= k) kiri++;   // the light one comes along
    kanan--;                               // the heavy one always goes
    perahu++;
}

Tracing for weights 1 2 3 4 5 and k = 6:

Three boats: {1, 5}, {2, 4}, and {3} alone.

Why this greedy is correct: the heaviest person must go; that cannot be avoided. The only question is whether they can have company. If even the lightest does not fit with them, nobody fits, so they go alone. If the lightest fits, pairing them never hurts — the light person is the easiest to pair with anyone, so "saving" them for later brings no benefit.

This "two pointers from opposite ends" pattern appears in many greedy problems.

How to convince yourself a greedy is correct

Three ways, from the fastest to the most convincing:

1. Look for a counterexample. Try odd small data: two equal elements, one very large element, all elements equal. A single failing example is enough to throw the plan away.
2. Test against a reference. Write a brute force that tries every possibility for n ≤ 8, then compare on thousands of random inputs (Chapter 10). This is the most practical way during a contest.
3. Exchange argument. Show that any best answer can be changed step by step into the greedy answer without making it worse. This is a real proof, and it is what was done for activity scheduling above.

Homework

Most common mistakes

OSN tips

Greedy almost always means "sort first". The real question is not "is this greedy" but "sorted by what". The four orderings below cover most greedy problems at the early levels:

Convince yourself with an exchange argument. Its shape is always the same: suppose there is a best answer whose order differs from the greedy choice; swap two adjacent parts; show the result does not get worse. If that swap can always be done, the greedy choice is certainly among the best answers. An argument that short is enough to tell a correct greedy apart from a greedy that happens to pass the samples.

Test the greedy with a brute force before submitting. For N ≤ 10, the brute force answer is certainly correct. Run both on hundreds of small random inputs and compare them with diff. A wrong greedy usually falls on the fifth or sixth random input — long before you lose time in the contest room.

If greedy fails, the problem is usually DP. A frequent sign: the current choice affects the choices available later in a way that cannot be summarized as a single number. Chapter 13 covers the replacement.

Note the difference between "as many as possible" and "as large as possible". Choosing the most activities is sorted by finish time; choosing activities with the largest total value cannot be done greedily and is indeed a DP problem. One word in the problem changes the entire approach.

Do not sort data whose order is part of the problem. If the answer requires the original index, store that index together with the data before sorting — for example as a pair. Losing the original index is a mistake that is only discovered after all the code is done.

Summary

• Greedy takes the best choice right now and never goes back; its standard form is sort followed by one pass, O(n log n).
• All of its difficulty lies in one question: sorted by what.
• A greedy that is correct for one set of data can be wrong for another — correctness belongs to the data, not to the shape of the problem.
• Three ways to check it: look for a small counterexample, test against a brute force reference on thousands of random inputs, and an exchange argument.
• Standard examples to recognize: making change, activity scheduling (sorted by finish time), and boat loading (two pointers from opposite ends).
• If greedy is shown to be wrong and no other sorting measure holds up, what is needed is dynamic programming in Chapter 13.

OSN-style exercises

All three are solved with one sort followed by one pass. What decides right or wrong is what is used as the sort key, so write down the exchange argument first before typing.

The skeletons for all three are in exercises/12/osn/.

Problem 1 — Service Queue

A counter can only serve one person at a time. That morning, all N customers were already present when the counter opened, and customer i needs Tᵢ minutes to be served. The clerk may call the customers in any order.

A customer's waiting time is how long they wait from when the counter opens until their service begins — not including their own service time. Find the smallest total waiting time that can be achieved.

Input format. The first line contains an integer N. The second line contains N integers T₁ T₂ … T_N.

Output format. One line containing the smallest total waiting time.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ Tᵢ ≤ 10,000

Sample input

3
5 1 3

Sample output

5

Explanation. The best order is 1, 3, 5. The first customer waits 0 minutes, the second customer 1 minute, the third customer 1 + 3 = 4 minutes. The total is 5. The order 5, 3, 1 gives a total of 0 + 5 + 8 = 13.

Skeleton: exercises/12/osn/01-antrian-layanan.cpp

Problem 2 — Checkpoints

Along a straight road there are N segments that must be monitored. Segment i stretches from kilometer Lᵢ to kilometer Rᵢ, including both ends.

The organizers will set up checkpoints at integer kilometer marks. A segment is considered monitored if at least one checkpoint stands inside that segment. Find the fewest number of checkpoints needed so that every segment is monitored.

Input format. The first line contains an integer N. Each of the next N lines contains two integers Lᵢ and Rᵢ.

Output format. One line containing the fewest number of checkpoints.

Constraints.

• 1 ≤ N ≤ 200,000
• 1 ≤ Lᵢ ≤ Rᵢ ≤ 10⁹

Sample input

4
1 3
2 5
4 7
6 9

Sample output

2

Explanation. One checkpoint at kilometer 3 monitors the first and second segments. Another checkpoint at kilometer 7 monitors the third and fourth segments. Two checkpoints cannot be reduced further, because the first and fourth segments share no kilometer.

Skeleton: exercises/12/osn/02-titik-pemeriksaan.cpp

Problem 3 — Load Pairing

There are 2N items that must be transported with N carts. Each cart carries exactly two items. The load of a cart is the sum of the weights of the two items in it.

The organizers want the heaviest cart to be as light as possible. Find the load of the heaviest cart in the best arrangement.

Input format. The first line contains an integer N. The second line contains 2N integers, the weight of each item.

Output format. One line containing the smallest possible load of the heaviest cart.

Constraints.

• 1 ≤ N ≤ 100,000
• 1 ≤ weight ≤ 10⁹

Sample input

3
3 5 2 8 1 4

Sample output

9

Explanation. The best arrangement pairs 1 with 8 (load 9), 2 with 5 (load 7), and 3 with 4 (load 7). The heaviest cart is 9. Another arrangement such as (8, 5), (4, 3), (2, 1) gives a heaviest cart of 13.

Skeleton: exercises/12/osn/03-pasangan-beban.cpp

Stuck or already done? Open the homework solutions page.