Suppose you're starting a radio show in the US. 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.
Each station covers a region, and there's overlap.
How do you figure out the smallest set of stations you can play on to cover all 50 states?
Getting the most optimal solution takes a long time:
- List every possible subset of stations (power set). There are
$2^n$ possible subsets. - From these, pick the set with the smaller number of stations that covers all 50 states.
Here's a greedy algorithm that comes pretty close and runs in
- Pick the station that covers the most states that haven't been covered yet. It's okay if it covers some states that have been covered already.
- Repeat until all the states are covered.