# 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wiki.hanzheteng.com/algorithm/cs/greedy-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.