贪心算法应用题

package com.zou.greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class Greedy {
    public static void main(String[] args) {
        //创建广播电视台，放入Map
        HashMap> broadcasts = new HashMap>();
        //将各地电视台放入到broadcasts
        HashSet hashSet1 = new HashSet();
        hashSet1.add("北京");
        hashSet1.add("天津");
        hashSet1.add("上海");
        HashSet hashSet2 = new HashSet();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        HashSet hashSet3 = new HashSet();
        hashSet3.add("城都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        HashSet hashSet4 = new HashSet();
        hashSet4.add("上海");
        hashSet4.add("天津");
        HashSet hashSet5 = new HashSet();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        //放入全部集合
        broadcasts.put("k1",hashSet1);
        broadcasts.put("k2",hashSet2);
        broadcasts.put("k3",hashSet3);
        broadcasts.put("k4",hashSet4);
        broadcasts.put("k5",hashSet5);
        //有所有地区的集合
        HashSet allAreas = new HashSet();
        allAreas.add("杭州");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("大连");
        allAreas.add("城都");
        allAreas.add("广州");
        allAreas.add("北京");
        allAreas.add("深圳");
        //创建需要的电台集合
        ArrayList selects = new ArrayList();
        //存放交集的临时集合
        HashSet tempSet = new HashSet();
        String masKey=null;
        //选出最大覆盖的
        while (allAreas.size()!=0){//看看又没选完
            //maskey要清空
            masKey=null;
            for (String key : broadcasts.keySet()) {
                tempSet.clear();
                //当前能覆盖的地区还有多少
                HashSet areas = broadcasts.get(key);
                //加入到临时集合
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas);//求tempSet和allAreas交集，会将allAreas交集部分复制给tempSet
                if (tempSet.size()>0&&(masKey==null||tempSet.size()>broadcasts.get(masKey).size())){
                    masKey=key;//重新赋key值
                }
            }
            //清除allAreas中已经拿到的城市
            if (masKey!=null){
                selects.add(masKey);
                allAreas.removeAll(broadcasts.get(masKey));
            }
        }
        System.out.println("得到的结果："+selects);
    }
}