# Greedy Algorithms

Using [dynamic programming](broken://pages/-LQpLufV5TWdpS8PjdK2) in most of the scenarios could be an overkill for optimization problems. A more efficient and simpler method could be adopted instead, which is [greedy algorithms](https://en.wikipedia.org/wiki/Greedy_algorithm). It will choose the best move in each step of solving sub-problems, in other words, a local optimal solution is made every time and hopefully it leads to the global optimal solution at the end.

## Activity Selection Problem

Assume there are *n* activities {a1, a2, ..., an} that all use the same room which is only available for one activity at a time. Each activity has a *starting time* si and a *ending time* fi. If two activities have no overlapping time frames then they are **compatible**, and a maximal compatible set of activities is required to compute at the end.

It is reasonable to solve this problem using [dynamic programming](broken://pages/-LQpLufV5TWdpS8PjdK2) approach with optimal substructure and solution scheme. However, there is an easy way to conquer this problem using [greedy](https://en.wikipedia.org/wiki/Greedy_algorithm) approach.

Intuitively, an activity is chosen that ends the first and spare as much time as possible for the rest of activities (there might be other greedy approaches, this only serves as an example). After the first greedy choice is made, the sub-problem needs to be considered that finding **compatible** activities following and by continuing doing so until the set is empty.

## Table of Contents

Though few scenarios can adopt greedy approaches, there are some proven interesting example problems solved using greedy approach:

* [Fractional Knapsack](https://github.com/aaronoah/algorithm-notes/tree/9a534ff48627c60fe225a120d7cf880d1d057006/docs/greedy-algorithms/fractional-knapsack.md) - classic knapsack problem with revision that items can be fractioned.
* [Huffman Coding](https://github.com/aaronoah/algorithm-notes/tree/9a534ff48627c60fe225a120d7cf880d1d057006/docs/greedy-algorithms/huffman-coding.md) - an efficient way to compress binary data by variable length coding.


---

# 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://cs-notes.gitbook.io/algorithm-notes/outline/overview-7.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.