> For the complete documentation index, see [llms.txt](https://wiki.hanzheteng.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.hanzheteng.com/algorithm/cs/greedy-algorithm.md).

# Greedy Algorithm

* Greedy algorithms are applied to optimization algorithms only.
* It picks always the current best solution; no backtracking.
* Not necessarily optimal --> need to prove it.

### Optimization Problem 

* find a set of items that can 
  * meet some constraints, and
  * optimize some objective function
* examples: shortest path, minimum spanning tree
* not an optimization problem: sorting

### Prove the Optimality

To prove the optimality of a greedy strategy, we need to prove the following two parts. 

* Greedy Choice
  * find the choice that is part of SOME optimal solution
  * there may exist multiple optimal solutions; no need to prove it for ANY optimal solution
* Optimal Substructure
  * After making the first choice, the final best solution is first choice + best solution for the rest of (compatible) input
  * We can solve the same optimization problem recursively!
  * Otherwise, we find a contradiction!

### Example problems

* activity selection (pick the earliest-finish task)
* minimum spanning tree
* Huffman code
* Dijkastra's shortest path
* graph coloring
* traveling salesman

### Greedy vs. Dynamic Programming 

* Greedy: always pick the current best
* DP: pick the best based on history
* You can always use DP to solve Activity Selection problem, but it is much costly (since you have to try all other branches)

### Example Code: Easy Swaps to Sort 123

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int n;
  std::cin >> n; 
  std::vector<int> candies(n);
  for (int k = 0; k < n; ++k)
    std::cin >> candies[k];

  // count total number of 1s, 2s, 3s
  int sum1 = 0, sum2 = 0, sum3 = 0;
  for (int k = 0; k < n; ++k){
    if (candies[k] == 1)
      sum1++;
    else if (candies[k] == 2)
      sum2++;
    else
      sum3++;
  }

  // all 3s should be placed in the range [sum1+sum2, n-1]
  // and then leave a subproblem of 1s and 2s in the range [0, sum1+sum2-1]
  int swap = 0;
  std::vector<int> temp_queue;
  for (int k = sum1 + sum2; k < n; ++k){
    if (candies[k] != 3){
      swap++;
      temp_queue.push_back(candies[k]);
    }
  }

  // move all 1s to the front and 2s to the end
  std::sort(temp_queue.begin(), temp_queue.end());

  // in [0, sum1+sum2-1], we want to put 1s to the front and 2s to the end 
  for (int k = sum1 + sum2 - 1; k >= 0; --k){
    if (candies[k] == 3){
      candies[k] = temp_queue.back();
      temp_queue.pop_back();
    }
  }

  // finally, count how many 2s are still there in the range [0, sum1-1]
  // which is supposed to be all 1s
  for (int k = 0; k < sum1; ++k){
    if (candies[k] == 2)
      swap++;
  }

  std::cout << swap << std::endl;

  return 0;
}
```