假设某节目要覆盖以下省份:
["广东", "广西", "海南", "福建", "湖南", "江西", "贵州", "云南"]
各个电视台的覆盖范围如下:
{
'TV1': {'湖南', '江西', '福建'},
'TV2': {'广西', '福建', '广东'},
'TV3': {'湖南', '海南', '贵州'},
'TV4': {'湖南', '江西'},
'TV5': {'云南', '贵州'},
}
解决思路:
-
step1: 选出一个覆盖了最多未覆盖省份的电视台,即使覆盖了已覆盖的省份也没关系
-
step2: 重复第一步,直到所有身份被覆盖
python 代码实现如下:
# 需要覆盖的省份
states_needed = set(["广东", "广西", "海南", "福建", "湖南", "江西", "贵州", "云南"])
# 每个电视台能覆盖的省份
stations = {}
stations["TV1"] = set(["福建", "湖南", "江西"])
stations["TV2"] = set(["广西", "福建", "广东"])
stations["TV3"] = set(["海南", "湖南", "贵州"])
stations["TV4"] = set(["湖南", "江西"])
stations["TV5"] = set(["贵州", "云南"])
# 选择合符条件的电视台加到这个集合中
final_stations = set()
# 循环一直运行到所有省份被覆盖
while states_needed:
best_station = None
states_covered = set() # 记录已覆盖的省份
for station, states in stations.items():
"""
stations 是电视台名
states 是电视台覆盖范围,数据类型为 set
"""
# python 的集合运算
# 得出:电视台覆盖的范围和实际要覆盖的范围的交集
covered = states_needed & states
# 找出覆盖省份最多的电视台
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
# 把已覆盖的省份从 states_needed 去掉
states_needed = states_needed - states_covered
# 把选择的电视台加到 final_stations 中
final_stations.add(best_station)
print(final_stations)
网友评论