2022-01-03

Greedy Algorithms

Greedy can tackle the impossible problems that have no fast solution (NP-complete problems)

Example of greedy

These examples below come from the book, Grokking Algorithms

The classroom scheduling problem

Suppose you have a classroom and want to hold as many classes here as possible.

The knapsack problem

Suppose you’re a greedy thief. You’re in a store with a knapsack, and there are all these items you can steal. But you can only take what you can fit in your knapsack. The knapsack can hold 35 pounds. You’re trying to maximize the value of the items you put in your knapsack. What algorithms do you use?

The set-covering problem

Suppose you’re starting a radio show. You want to reach listeners in all 50 states. You have to decide what stations to play on to reach all those listeners. It costs money to be on each station, so you’re trying to minimize the number of stations you play on.

If we list every possible subset of stations, this is called the power set. There are 2^n possible subsets. It takes O(2^n) time.

Travelling salesman problem

Exercises

1. 253 Meeting Rooms II - Free active meeting rooms before current interval. Sort with start time. Use priority_queue to keep active meeting rooms in ascending order with end time. [CAUTION] std::less is default for descending order in C++ STL.
   • sort(,,{})
   • priority_queue<T,,std::?>
2. 44 Wildcard Matching
3. 1011 Capacity To Ship Packages Within D Days
4. 1167 Minimum Cost to Connect Sticks
5. 316 Remove Duplicate Letters
6. 581 Shortest Unsorted Continuous Subarray
7. 402 Remove K digits
8. 769 Max Chunks To Make Sorted
9. 1509 Minimum Difference Between Largest and Smallest Value in Three Moves
10. Find Original Array From Doubled Array