1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class BaseStation {
  public static void main(String[] args) {
    String[] area = new String[]{"台北", "台東", "彰化", "花蓮", "高雄","澎湖","苗栗","宜蘭"};
    List areaList = new ArrayList(Arrays.asList(area));
    List<List<String>> baseStation = new ArrayList<>();
    baseStation.add(0, Arrays.asList("台北", "台東", "彰化"));
    baseStation.add(1, Arrays.asList("花蓮", "高雄", "澎湖"));
    baseStation.add(2, Arrays.asList("苗栗", "宜蘭", "台北"));
    baseStation.add(3, Arrays.asList("苗栗", "高雄"));
    baseStation.add(4, Arrays.asList("澎湖","宜蘭"));
    List<Integer> result = new ArrayList<>();
    // 刪到所有涵蓋範圍為0，才停止。
    while (areaList.size() > 0) {
      // 此次最大涵蓋的基地台編號
      int maxKey = -1;
      // 基地台涵蓋數量
      int maxCnt = 0;
      // 遍歷所有基地台
      for (int i = 0; i < baseStation.size(); i++) {
        // 基地台涵蓋地區清單
        List subList = baseStation.get(i);
        // 涵蓋地區數量
        int count = contains(areaList, subList);
        // 此基地台涵蓋數量是否為最大?
        if (count > maxCnt) {
          maxKey = i;
          maxCnt = count;
        }
      }
      // 所有地區包含在「最大涵蓋的基地台」地區範圍，則刪除
      containsRemove(areaList, baseStation.get(maxKey));
      // 儲存最大涵蓋的基地台
      result.add(maxKey);
    }
    System.out.println("result=" + result);
  }
  // 涵蓋地區數量計算
  public static int contains(List<String> areaList,List<String> subList) {
    int count = 0;
    for (int i = 0; i < areaList.size(); i++) {
      if (subList.contains(areaList.get(i))) {
        count++;
      }
    }
    return count;
  }
  // 所有地區包含在「最大涵蓋的基地台」地區範圍，則刪除
  public static void containsRemove(List<String> areaList,List<String> subList) {
    for (int i = 0; i < subList.size(); i++) {
      if (areaList.contains(subList.get(i))) {
        areaList.remove(subList.get(i));
      }
    }
  }
}