这篇文章我们共同学习贪婪算法，贪婪策略是一种非常简单的问题解决策略。

教室调度问题

假设目前有如下的课程表，你希望将尽可能多的课程安排在某间教室上。

如果我们安排了美术课之后，英语课就不能安排到这间教室了

你希望在这间教室上尽可能多的课，那么如何选出尽可能多且时间不冲突的课程呢？

排课信息

具体做法在这里先给你：

1、 先选出结束最早的课，即就是这间教室上的第一堂课

2、 由于第一节课是10点结束的，因此我们要选从第一节课结束的时间才开始上的课，同样，我们选出结束最早的课，这将是这间教室上的第二堂课

重复第二步，这样我们就能找出这间教室既不冲突也可以安排尽可能多的课。

于是，我们就得出了这间教室可以上三堂课，如图所示：

排课结果

你看到这里一定会说这有啥难的！但这就是贪婪算法的优势——简单易行，因为每一步都是局部最优解，那么最终得到的就是全局最优解。当然贪婪算法有其局限性，正是其简单易实现的优点才没有被弃用。

我们再看一个问题——集合覆盖问题

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

每个广播台播出都需要支付费用，因此要力图在尽可能少的广播台播出并且覆盖的州要尽可能多。

每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠

地区

是不是想想都挺难的，但是贪婪算法可以解决这一问题，具体做法：

1、 选出覆盖了最多的地区的广播台，即使下次选择的广播台已经覆盖了上次已经覆盖过的地区，也没有关系，只要它是覆盖最多的就可以。

2、 重复第一步，直到覆盖了所有的地区

这是一种近似算法。在获得精确解需要的时间太长时，可使用近似算法。判断近似算法优劣的标准如下：

i. 速度有多快

ii. 得到的近似解与最优解的接近程度

贪婪算法不仅简单，而且通常运行速度很快。

代码实现

package ShangGuiGu.Algorithm.Greedy;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;/*** 贪心算法*/public class GreedyAlgorithm {public static void main(String[] args) {//存储所有广播台HashMap<String, HashSet<String>> broadcasts = new HashMap<>();//列出各个广播台所覆盖的地区HashSet<String> k1 = new HashSet<>();k1.add("北京");k1.add("上海");k1.add("天津");HashSet<String> k2 = new HashSet<>();k2.add("广州");k2.add("北京");k2.add("深圳");HashSet<String> k3 = new HashSet<>();k3.add("成都");k3.add("上海");k3.add("深圳");HashSet<String> k4 = new HashSet<>();k4.add("上海");k4.add("天津");HashSet<String> k5 = new HashSet<>();k5.add("杭州");k5.add("大连");broadcasts.put("k1",k1);broadcasts.put("k2",k2);broadcasts.put("k3",k3);broadcasts.put("k4",k4);broadcasts.put("k5",k5);//需要覆盖的地区HashSet<String> cities = new HashSet<>();// cities=getCities(broadcasts);cities.add("北京");cities.add("上海");cities.add("天津");cities.add("广州");cities.add("深圳");cities.add("成都");cities.add("杭州");cities.add("大连");//标记覆盖地区最多的广播台String maxKey=null;//存储“当前”广播台在“剩余”的地区中能覆盖的地区HashSet<String> tempSet = new HashSet<>();//存储每一次for循环，选取的广播台ArrayList<String> broadcastsList = new ArrayList<>();//当所有的地区都已经覆盖完，结束while (cities.size()!=0){for (String key:broadcasts.keySet()){//当前广播台覆盖的地区HashSet<String> curCities = broadcasts.get(key);//存储当前广播台覆盖的地区tempSet.addAll(curCities);//存储“当前”广播台在“剩余”的地区中能覆盖的地区==curCities与cities的交集tempSet.retainAll(cities);//检测到当前广播台包含的未覆盖的地区数量，比maxKey广播所包含的地区还多if (tempSet.size()>0&&(maxKey==null||tempSet.size()>broadcasts.get(maxKey).size())){maxKey=key;}//清空当前广播台覆盖的地区，为下一次for循环tempSet.clear();}//选取到一个包含未覆盖地区最多的广播台if (maxKey!=null){broadcastsList.add(maxKey);//选取的广播已经覆盖了一部分未覆盖的地区，剩下的即为未覆盖的地区，用于下一次forEach循环cities.removeAll(broadcasts.get(maxKey));}//下一次wihle循环maxKey=nullmaxKey=null;}//打印选取的广播台System.out.println("选取的广播台："+broadcastsList);}/*** 得到所有广播所覆盖的地区集合* @param broadcasts* @return*/public static HashSet<String> getCities(HashMap<String,HashSet<String>> broadcasts){HashSet<String> cities = new HashSet<>();for (HashSet<String> curCities:broadcasts.values()){cities.addAll(curCities);}return cities;}}