如何基于人员可用时间生成会议调度？贪心算法适配问题

问题背景 #

给定条件 #

一个存储人员可用时间与会议时长的字典：

• 键：人员姓名
• 值：[开始时间（包含）、结束时间（不包含）、会议时长]
  其中开始时间、结束时间为≥0的整数，会议时长为≥1的整数

调度规则 #

1. 会议不可拆分，必须完成全部时长的安排；
2. 题目保证存在有效调度方案；
3. 若多个人员可在同一时段安排，需严格遵循原字典中的姓名顺序。

示例 #

输入：

{ "John": [1, 3, 2], "Mary": [0, 4, 1], "Peter": [2, 6, 2], "Susan": [3, 4, 1] }

输出：

["Mary", "John", "John", "Susan", "Peter", "Peter"]

问题疑问 #

原本计划用贪心算法，按「最早可用结束时间」排序填充调度，但遇到可用区间时长大于实际会议时长的情况时不知道如何处理。

解决方案 #

你的贪心思路方向正确，只需调整策略细节，就能解决区间时长过剩的问题，核心逻辑如下：

核心策略 #

优先安排可用窗口结束时间最早的人员；若结束时间相同，则严格遵循原字典的姓名顺序。同时跟踪每个人的剩余会议时长，直到完成全部安排。

具体步骤 #

1. 预处理数据

   • 将原始字典转换为包含「姓名、可用开始时间、可用结束时间、剩余会议时长、原顺序索引」的列表，原顺序索引用于保证同优先级下的排序符合要求。
   • 计算调度总时长：取所有人员可用结束时间的最大值，以此作为调度数组的长度（示例中最大值为6，因此需要填充6个时间点）。

2. 逐时段填充调度
   对每个时间点t（从0到总时长-1）执行以下操作：

   • 筛选候选人：找出满足t >= 可用开始时间、t < 可用结束时间且剩余会议时长 > 0的人员。
   • 排序候选人：先按「可用结束时间」升序排序，结束时间相同则按「原顺序索引」升序排序。
   • 选中并更新状态：取排序后的第一个人员，将其姓名加入当前时间点的调度结果，同时把该人员的剩余会议时长减1。

解决区间时长过剩的问题 #

当人员的可用区间时长大于会议时长时（比如示例中Mary的可用区间是0-4，时长4，但会议仅需1），该策略会在最早的可行时间点安排她，之后她的剩余时长变为0，会被自动排除在后续的候选人筛选之外，剩余时段自然留给其他需要安排的人员，完全符合规则。

示例验证（对应输入输出） #

• 时间0：候选人仅Mary（结束时间4，剩余1，索引0），选中Mary，剩余时长变为0。
• 时间1：候选人仅John（结束时间3，剩余2，索引1），选中John，剩余时长变为1。
• 时间2：候选人有John（结束时间3，剩余1，索引1）、Peter（结束时间6，剩余2，索引2），John结束时间更早，选中John，剩余时长变为0。
• 时间3：候选人有Susan（结束时间4，剩余1，索引3）、Peter（结束时间6，剩余2，索引2），Susan结束时间更早，选中Susan，剩余时长变为0。
• 时间4-5：候选人仅Peter（结束时间6，剩余2→1→0，索引2），连续选中Peter两次。
  最终得到的调度结果与示例完全一致。

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