第 15 题

while i < len(orders) and con1(orders[i][1]) <= now:
    tp = orders[i][3]
    dur = orders[i][2]
    ②
    if chef != -1:
        assign(chef, i, now)
    else:
        wait.append([i, tp, dur])
    i += 1

内层循环按到达顺序处理时间不晚于 now 的订单，tp 取当前订单的菜品类型。空②产生后续分支使用的 chef：不是 -1 就调用 assign(chef, i, now)，否则把订单下标、菜品类型和耗时放入 wait。处理后 i 加 1，转向下一条尚未接收的订单。这里 i、oid 保存的是 orders 的列表下标，与从 1 开始的订单编号不是同一个量。

遇到 assign(chef, i, now) 时，转入该函数。它先执行：

dur = orders[oid][2]
et = st + dur
orders[oid][1] = con2(st)
orders[oid].append(con2(et))
orders[oid].append(-1)
idle[chef] = False
insert_work(et, chef)

st 是实际开始时间，et 是结束时间。订单原有 4 个数据项，因此两次 append 分别新增下标 4、5 的字段；下标 1 原先保存到达时间，此时改为实际开始时间。厨师被标记为忙碌，工作记录按结束时间插入 work。

随后执行该厨师订单记录的首尾处理：

if head[chef] == -1:
    head[chef] = oid
else:
    ①
tail[chef] = oid

空表时直接把当前订单设为首结点，每次都把当前订单设为尾结点。结合 head、tail 和新增的 -1 字段，可知程序用 orders 中的记录构造每位厨师的订单链表：head、tail 保存首尾订单的下标，下标 5 的字段用于保存后继订单的下标，-1 表示没有后继。记录扩展后的结构是：

完成分配后返回接单循环；等待订单后来调用 assign 时，也使用相同的记录和链接方式。

new_work = []
for et, cid in work:
    if et <= now:
        idle[cid] = True
        if wait:
            for k in range(len(wait)):
                woid, wtp, wdur = wait[k]
                chef = find_chef(wtp)
                if chef != -1:
                    assign(chef, woid, now)
                    wait.pop(k)       # pop：弹出索引k处的元素
                    break
    else:
        new_work.append([et, cid])
work = new_work

接收当前时刻已到达的订单后，程序按 work 中的顺序检查结束时间。et <= now 时立即将该厨师标为空闲，并从 wait 的队首向后查找可分配的订单；找到后调用 assign，把订单交给找到的厨师，再用 pop(k) 从等待队列中移除，break 结束本次等待队列扫描。等待更久且当前可以处理的订单因而先被检查。

尚未结束的工作记录进入 new_work，最后用它更新 work。这里释放厨师和给等待订单派单是交替进行的，并未先把本时刻全部结束的厨师统一标为空闲。

③
if i < len(orders):
    now = min(now, con1(orders[i][1]))
if work:
    now = min(now, work[0][0])

完成当前时刻的处理后，空③更新now。其后的两个min分别用下一条订单到达时间、最早工作结束时间限制更新后的时刻，避免越过尚未处理的事件。