多学生版Course Scheduling III：求最大选课数及课程分配方案

问题定义 #

给定n门编号为0~n-1的在线课程，每门课程用courses[i] = [duration_i, lastDay_i]表示：需要连续学习duration_i天，且必须在lastDay_i当天或之前完成。另有p名学生，均从第1天开始学习。需返回最多可修读的课程总数，以及具体的课程分配方案（即每门选中课程对应的学生编号）。

核心思路 #

单学生版本的解法是「贪心排序+大顶堆」，多学生版本则是把这个逻辑扩展到p个学生：为每个学生维护一个独立的「已选课程堆」，优先给当前总学习时长最短的学生安排课程，必要时替换该学生已选课程中耗时最长的那门，以此最大化课程数量。

分步解法 #

1. 课程排序
   先将所有课程按lastDay从小到大排序。这是贪心策略的核心：截止日期越早的课程越容易错过，优先处理能避免后期无法安排。

2. 维护学生学习状态
   为每个学生维护两个信息：

   • 一个大顶堆：存储该学生已选课程的耗时，堆顶是耗时最长的课程（方便快速替换）
   • 一个总时长变量：记录该学生已选课程的总学习天数
     同时用一个小顶堆来维护所有学生的总时长，能快速找到当前总时长最短的学生，提升效率。

3. 逐个安排课程
   遍历排序后的每门课程：

   • 取出当前总时长最短的学生，尝试将课程分配给他：
     • 如果学生总时长 + 当前课程时长 <= 当前课程截止日，直接将课程加入该学生的大顶堆，更新总时长
     • 如果不满足上述条件，但该学生的大顶堆不为空，且堆顶课程的耗时 > 当前课程时长：
       • 替换堆顶课程：弹出堆顶，加入当前课程，更新总时长（总时长 = 原总时长 - 堆顶耗时 + 当前课程耗时）
     • 如果以上两种情况都不满足，跳过该课程，尝试下一门

4. 生成结果

   • 统计所有学生堆中元素的总数，即为最多可修读的课程数
   • 维护一个assignment数组，记录每门选中课程对应的学生编号（未选中的课程可标记为-1）

示例说明 #

假设p=2，课程列表为：
courses = [[2,4], [3,5], [1,3], [4,6]]
排序后的课程顺序为：[1,3]（编号2）、[2,4]（编号0）、[3,5]（编号1）、[4,6]（编号3）

• 处理课程2：分配给学生0，总时长1，堆：[1]
• 处理课程0：分配给学生1，总时长2，堆：[2]
• 处理课程1：分配给总时长最短的学生0，1+3=4 ≤5，加入后总时长4，堆：[3,1]
• 处理课程3：分配给总时长最短的学生1，2+4=6 ≤6，加入后总时长6，堆：[4,2]

最终结果：最多修读4门课，分配方案为课程2→0，课程0→1，课程1→0，课程3→1

关键优化点 #

• 用小顶堆维护学生总时长，能在O(log p)时间内找到最优分配的学生
• 替换操作的本质是用更短的课程占用更少的时间，不减少课程数量的同时，为后续课程腾出更多空间

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