这篇文章我们共同学习贪婪算法，贪婪策略是一种非常简单的问题解决策略。
教室调度问题
假设目前有如下的课程表，你希望将尽可能多的课程安排在某间教室上。
如果我们安排了美术课之后，英语课就不能安排到这间教室了
你希望在这间教室上尽可能多的课，那么如何选出尽可能多且时间不冲突的课程呢？
具体做法这里给你：
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> broadcasts = new HashMap<>();
//列出各个广播台所覆盖的地区
HashSet k1 = new HashSet<>();
k1.add("北京");
k1.add("上海");
k1.add("天津");
HashSet k2 = new HashSet<>();
k2.add("广州");
k2.add("北京");
k2.add("深圳");
HashSet k3 = new HashSet<>();
k3.add("成都");
k3.add("上海");
k3.add("深圳");
HashSet k4 = new HashSet<>();
k4.add("上海");
k4.add("天津");
HashSet 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 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 tempSet = new HashSet<>();
//存储每一次for循环，选取的广播台
ArrayList broadcastsList = new ArrayList<>();
//当所有的地区都已经覆盖完，结束
while (cities.size()!=0){
for (String key:broadcasts.keySet()){
//当前广播台覆盖的地区
HashSet 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=null
maxKey=null;
}
//打印选取的广播台
System.out.println("选取的广播台："+broadcastsList);
}
/**
* 得到所有广播所覆盖的地区集合
* @param broadcasts
* @return
*/
public static HashSet getCities(HashMap> broadcasts){
HashSet cities = new HashSet<>();
for (HashSet curCities:broadcasts.values()){
cities.addAll(curCities);
}
return cities;
}
}