题目重点：每笔需求持续占一个资源，半开区间端点相接可以复用。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每interval(start,end)满足start<end，全部必须接受；资源完全同质，不允许中途迁移。
- 固定K时可能无法接受全部；是否可拒绝、最大接受数或优先客户未给，不能自动把本答案作为固定K的完整政策。
解题路线
- 按start排序，active最小堆存(end,id)，开始前释放所有end≤start资源到freeID堆，取最小空闲ID，否则创建新资源。
- 需要新资源时全部已有资源都被同时占用，所以此时重叠数形成台数下界；算法只在必要时新建，达到全局最小。
- assignment按原输入index返回，处理同start用原顺序使结果确定。只求数时可扫事件或维护end堆；真正租车还有地点/车型等约束，未给时不掺入本模型。
手动走一遍
[1,3)、[2,4)、[3,5)：第一/第三可同资源，第二另一资源，共2。固定K1时不能满足前两同时；明确返回不可行、拒绝策略或调度选择，不能悄悄创建第二台。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush,heappop
def allocate(intervals):
if any(start>=end for start,end in intervals):raise ValueError("positive-duration half-open intervals required")
active,free=[],[];created=0;assignment=[None]*len(intervals)
for index,(start,end) in sorted(enumerate(intervals),key=lambda row:(row[1][0],row[0])):
while active and active[0][0]<=start:
_,car=heappop(active);heappush(free,car)
if free:car=heappop(free)
else:car=created;created+=1
assignment[index]=car;heappush(active,(end,car))
return created,assignment
复杂度
O(nlogn)时间/O(n)空间含两堆及结果；默认最小可用ID选择增加free堆成本。
易错点与追问
容易失分的边界
- 结束等起点是否复用由端点合同决定。
- 用最长会议/租期优先而不按开始处理不能应用重叠下界证明。
继续深挖
- 不同车可用起始地点导致转场时间，怎样扩展匹配模型？
- 允许拒绝但优化总利润时，为什么不是简单会议数问题？
