题目重点：题目给每门课开始结束时间和 credit、最多选 K 门；明确半开时间冲突语义后用带课程数维度的加权区间 DP。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版时间段为半开 [start,end)，所以前课 end=后课 start 可以连续选择；课程必须满足 end>start。
- 最多 K 门，不要求恰好 K 门；学分可负，最佳可选 0 门得 0。若要求恰好 K 门，初始化和无解规则不同。
- 课程互不冲突的定义仅按时间，不考虑地点、跨校区通勤或先修依赖。
解题路线
- 按结束时间排序课程，令 p(i) 为第 i 门之前结束时间≤本门开始时间的课程数量，使用二分查找。
- dp[i][k] 表示前 i 门课程里至多选 k 门的最高学分。跳过第 i 门取 dp[i−1][k]；选它取 credit_i+dp[p(i)][k−1]；两者取大。
- dp 的 k=0 与 i=0 都为 0；负学分自然会被跳过。若课程很多而 K 很小，只计算到 min(K,N)。
- 用随机小输入枚举全部课程子集，按时间冲突与门数过滤，对照 10,000 组，覆盖接触端点、负学分和 K=0。
手动走一遍
课程 A=[1,3)、credit=4；B=[3,5)、credit=6；C=[2,4)、credit=9，K=2。A+B 不冲突，得 10；C 与两者都冲突，只得 9；答案 10。若时间端点不能接续，A+B 将冲突，答案改变，需先问。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Weighted interval scheduling with at most K courses."""
from bisect import bisect_right
def max_credits(courses: list[tuple[int, int, int]], limit: int) -> int:
if limit < 0 or any(end <= start for start, end, _ in courses):
raise ValueError("invalid course or limit")
ordered = sorted(courses, key=lambda item: (item[1], item[0]))
ends = [end for _, end, _ in ordered]
n = len(ordered)
cap = min(limit, n)
dp = [[0] * (cap + 1) for _ in range(n + 1)]
for i, (start, _, credit) in enumerate(ordered, 1):
compatible_count = bisect_right(ends, start, 0, i - 1)
for k in range(1, cap + 1):
dp[i][k] = max(dp[i - 1][k], credit + dp[compatible_count][k - 1])
return dp[n][cap]
复杂度
N 门课排序 O(N log N)，每门二分前驱 O(log N)，DP O(N min(K,N)) 时间与空间；当 K≥N 可退化为普通一维加权区间调度 O(N) DP 空间。
易错点与追问
容易失分的边界
- 误用 Course Schedule DAG 拓扑排序；本题是时间区间选择。
- 按 credit 贪心取最大的 K 门，可能选到互相冲突的课程。
- 只写一维 dp，忘记最多 K 门的额外状态。
- bisect 前驱时把 end=start 当冲突或无冲突却未说明。
- 最多 K 门误解成必须 K 门，负学分时答案错误。
继续深挖
- 若要求恰好 K 门且无解，DP 应如何初始化？
- 若课程还有先修关系，同时受时间约束，问题如何改变？
- 若同一课程可选多个时段，怎样避免重复选课程？
