Skip to content

Greedy

This page briefly introduces greedy algorithms.

Introduction

A greedy algorithm has the computer simulate the way a greedy person makes decisions. This person is extremely greedy: at every step they take the action that is best by some measure. They are also short-sighted: they only ever look at what is in front of them and never consider what consequences a choice may have later.

As you would expect, the greedy method does not always find an optimal solution, so whenever you use it, make sure you can prove that it is correct.

Explanation

When it applies

Greedy algorithms work especially well on problems with optimal substructure. Optimal substructure means that the problem can be solved by breaking it into subproblems, and that optimal solutions to the subproblems carry forward to an optimal solution to the final problem.1

Proof

Common proof techniques include the exchange argument and mathematical induction; the two can also be combined.

  1. Exchange argument: start from an arbitrary optimal solution and turn it into the solution found by the greedy algorithm through finitely many exchanges or replacements, each of which preserves feasibility and does not make the objective value worse. This proves that the greedy solution is optimal as well. The proof is often written as a proof by contradiction.
  2. Induction: first compute the optimal solution \(F_1\) for the base case (for example \(n = 1\)), then prove that for every \(n\), \(F_{n+1}\) can be derived from \(F_{n}\).

Key points

Common problem types

In problems up to the difficulty of the Senior division, two kinds of greedy algorithm are the most common.

  • Sort XXX in some order, then choose in some order (for example, from smallest to largest).
  • Repeatedly take the largest/smallest thing in XXX and update XXX. (Taking the maximum/minimum can sometimes be optimized, for example by maintaining it with a priority queue.)

The difference is that the first kind is always offline: you can process everything first and choose afterwards. The second kind may be online, so you have to choose as you process.

Greedy by sorting

The sorting method, or adjacent exchange method, typically applies when the input is an array whose elements carry a few weights each (usually one or two): sort the array, then traverse it and simulate the computation to find the optimal value.

Example: NOIP 2012 King's Game

It is the national day of country H, and the king has invited \(n\) ministers to play a game with prizes. First, he has every minister write an integer on his left hand and another on his right hand, and the king writes an integer on each of his own hands as well. Then the \(n\) ministers line up, with the king at the very front of the line. Once they are lined up, every minister receives some gold coins from the king: the number of coins a minister receives is the product of the numbers on the left hands of everyone in front of him, divided by the number on his own right hand, rounded down.

The king does not want any one minister to receive an especially large reward, so he asks you to rearrange the line so that the minister who receives the most receives as little as possible. Note that the king always stays at the very front of the line.

Approach

Let \(a_i\) and \(b_i\) be the numbers on the left and right hands of the \(i\)-th minister in the current permutation. We derive the greedy strategy by the adjacent exchange method.

Ignore the floor for now, and let \(s\) be the product of the \(a_i\) of everyone in front of the \(i\)-th minister. Before the swap, the larger of the two ministers' rewards is

\[ \dfrac{s}{b_i b_{i+1}}\max(b_{i+1},a_i b_i),\tag{1} \]

After the swap, the larger of the two is

\[ \dfrac{s}{b_i b_{i+1}}\max(b_i,a_{i+1}b_{i+1}).\tag{2} \]

If \(a_i b_i\le a_{i+1}b_{i+1}\), then since \(b_{i+1}\le a_{i+1}b_{i+1}\), expression \((1)\) is no greater than expression \((2)\). The floor function is monotone and \(\max(\lfloor u\rfloor,\lfloor v\rfloor)=\lfloor\max(u,v)\rfloor\), so swapping the two ministers does not make the largest reward smaller. Sorting by \(a_i b_i\) in ascending order is therefore optimal.

In the implementation, we store the two input numbers in a struct and overload an operator:

1
2
3
4
5
struct uv {
  int a, b;

  bool operator<(const uv& x) const { return 1LL * a * b < 1LL * x.a * x.b; }
};

Greedy with undo

The idea is to accept each new option provisionally; if a constraint is then violated, undo the option in the chosen set that is worst by the greedy criterion. The strategy still needs a proof of correctness.

Example: [USACO09OPEN] Work Scheduling

John's working day starts at time \(0\) and has \(10^9\) units of time. In any unit of time he may pick any one of \(N(1 \leq N \leq 10^5)\) jobs, numbered \(1\) to \(N\), and complete it. Job \(i\) has deadline \(D_i(1 \leq D_i \leq 10^9)\) and brings a profit of \(P_i( 1\leq P_i\leq 10^9 )\) once completed. Given the profits and deadlines of the jobs, find the maximum profit John can obtain.

Approach
  1. First assume that every job gets done: sort the jobs by deadline and push them into the queue in that order.
  2. When deciding whether to do job i, if its deadline meets the condition, compare the job with the lowest-paying element in the queue. If job i pays more, we undo the earlier choice: ans += a[i].p - q.top().
    A priority queue (a min-heap) keeps the smallest element at the front of the queue.
  3. The condition a[i].d<=q.size() can be read as follows: only a[i].d jobs fit into the period from 0 to a[i].d, and q.size()>=a[i].d means that completing q.size() jobs takes at least a[i].d time. So when job i is the more profitable one, the least profitable job should be swapped out of the priority queue.
Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

struct f {
  long long d;
  long long p;
} a[100005];

bool cmp(f A, f B) { return A.d < B.d; }

// a min-heap maintains the minimum
priority_queue<long long, vector<long long>, greater<long long>> q;

int main() {
  long long n, i;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> a[i].d >> a[i].p;
  }
  sort(a + 1, a + n + 1, cmp);
  long long ans = 0;
  for (i = 1; i <= n; i++) {
    if (a[i].d <= (int)q.size()) {  // past the deadline
      if (q.top() < a[i].p) {       // undo an earlier choice
        ans += a[i].p - q.top();
        q.pop();
        q.push(a[i].p);
      }
    } else {  // add it to the queue directly
      ans += a[i].p;
      q.push(a[i].p);
    }
  }
  cout << ans << endl;
  return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from heapq import heappush, heapreplace

a = [tuple(map(int, input().split())) for _ in range(int(input()))]
a.sort(key=lambda job: job[0])  # sort by deadline in ascending order

ans = 0  # total profit
q = []  # a min-heap maintains the minimum
for d, p in a:
    if d <= len(q):  # past the deadline
        if q[0] < p:  # undo an earlier choice
            ans += p - heapreplace(q, p)
    else:  # add it to the queue directly
        ans += p
        heappush(q, p)
print(ans)
Complexity analysis
  • Space complexity: with \(n\) jobs in the input, the array \(a\) uses \(n\) elements, and in the worst case the priority queue stores \(n\) elements, so the space used is \(O(n)\).
  • Time complexity: std::sort takes \(O(n\log n)\) and maintaining the priority queue takes \(O(n\log n)\), so the algorithm runs in \(O(n\log n)\) overall.

Difference from dynamic programming

An ordinary greedy algorithm relies on local choices that can be proved safe; dynamic programming instead maintains the optimal value of every state and compares the candidate transitions.

Practice problems

References and notes