基于员工偏好哈希表，筛选覆盖最多员工的两日培训日期

问题背景 #

给定员工偏好字符串列表P，其长度等于员工总数。需从0-9这10个候选日期中选择2天开展培训，每位员工提供的字符串由0-9数字组成，代表其可参加的日期。目标是找出能覆盖最多员工的两日组合（最优为覆盖全部员工）。

举个例子，输入P = ["0123", "012", "23", "256", "689", "1567"]时，各日期覆盖员工情况如下：

• 日期0：员工0、1
• 日期1：员工0、1、5
• 日期2：员工0、1、2、3
• 日期3：员工0、2
• 日期4：无员工
• 日期5：员工3、5
• 日期6：员工3、4、5
• 日期7：员工5
• 日期8：员工4
• 日期9：员工4

其中日期2和6的组合能覆盖全部6名员工，是最优解。

核心思路 #

单个日期的覆盖员工数无法直接判断组合优劣——因为两个日期可能覆盖大量重复员工。正确的做法是计算任意两日组合覆盖员工的并集大小，并找出并集最大的组合。

具体实现步骤 #

1. 将每个日期对应的员工列表转换为集合：集合的并集操作能快速去重，高效计算实际覆盖的员工数量。
2. 遍历所有有效的两两日期组合：跳过无员工选择的日期，且通过i < j的遍历逻辑避免重复计算同一组合（比如(2,6)和(6,2)只算一次）。
3. 计算每个组合的覆盖数：对每对日期，计算其员工集合的并集大小。
4. 记录最优组合：始终保存当前覆盖数最大的日期组合，若找到覆盖全部员工的组合可直接返回，无需继续计算。

完整代码实现 #

def find_days(prefs):
    # 初始化日期到员工集合的映射
    preferences = {}
    total_employees = len(prefs)
    
    # 遍历员工偏好，填充映射字典
    for emp_idx, available_days in enumerate(prefs):
        for day in available_days:
            if day in preferences:
                preferences[day].add(emp_idx)
            else:
                preferences[day] = {emp_idx}
    
    max_coverage = 0
    best_combination = (None, None)
    
    # 获取所有有员工选择的日期
    valid_days = list(preferences.keys())
    if not valid_days:
        return best_combination
    
    # 遍历所有两两日期组合
    for i in range(len(valid_days)):
        day1 = valid_days[i]
        set1 = preferences[day1]
        for j in range(i + 1, len(valid_days)):
            day2 = valid_days[j]
            set2 = preferences[day2]
            # 计算当前组合的覆盖员工数
            current_coverage = len(set1.union(set2))
            # 更新最优组合
            if current_coverage > max_coverage:
                max_coverage = current_coverage
                best_combination = (day1, day2)
                # 提前终止：已覆盖所有员工，无需继续计算
                if max_coverage == total_employees:
                    return best_combination
    
    # 处理只有单个有效日期的极端情况
    if len(valid_days) == 1:
        best_combination = (valid_days[0], None)
    
    return best_combination

代码优化说明 #

• 用集合替代列表：集合的union操作时间复杂度更低，去重逻辑更高效。
• 提前终止逻辑：一旦找到覆盖全部员工的组合，直接返回结果，减少不必要的计算开销。
• 跳过无效日期：无员工选择的日期不会参与组合计算，节省遍历时间。
• 避免重复计算：通过i < j的遍历方式，每个日期组合仅计算一次，提升效率。

内容的提问来源于stack exchange，提问作者Siggyweb