You need to enable JavaScript to run this app. Google Code Jam Parenting Partnering Returns题代码样例正确但测试用例不通过排查
优惠活动
大模型
产品
解决方案
定价
更多

Google Code Jam Parenting Partnering Returns题代码样例正确但测试用例不通过排查

问题说明

这是Google Code Jam的双资源区间调度类题目,核心需求是把所有任务分配给C和J两个执行方,要求两个执行方的任务时间不能重叠,无法完成分配时输出IMPOSSIBLE。
当前提交的代码在样例测试下输出正确,但无法通过正式测试用例校验,需要定位代码缺陷。

现有提交代码
def chores(n):
    l=[]
    for i in range(n):
        l.append(list(map(int,input().split())))
    s=[" "]*len(l)
    new=l[:]
    new=sorted(new)
    C_start=new[0][0]
    C_end=new[0][1]
    ind=l.index(new[0])
    s[ind]="C"
    C=1
    J=0
    for i in range(1,n):
        if new[i][0]>=C_end:
            ind=l.index(new[i])
            s[ind]="C"
            C_start=new[i][0]
            C_end=new[i][1]
        elif new[i][0]<C_end and J==0:
            ind=l.index(new[i])
            s[ind]="J"
            J=1
            J_start=new[i][0]
            J_end=new[i][1]
        elif new[i][0]>=J_end:
            ind=l.index(new[i])
            s[ind]="J"
            J_start=new[i][0]
            J_end=new[i][1]
            
        else:
            return "IMPOSSIBLE"
    return "".join(s)   

tests = int(input())
ans=[]
for t in range(tests):
    n=int(input())
    ans.append(chores(n))
for i in range(0,tests):
    print("Case #{}: {}".format(i+1,ans[i]))
核心缺陷定位
  • 索引匹配逻辑存在硬伤:代码使用list.index()方法匹配排序后任务在原始列表中的位置,但该方法只会返回列表中第一个匹配到的元素索引。当存在多个起止时间完全相同的任务时,所有重复任务都会被匹配到同一个原始位置,其余重复任务对应的分配位置永远无法被填充,最终输出的分配字符串会出现空位、长度错误的问题。
  • 分支判断逻辑存在冗余漏洞:代码对J的状态硬编码了初始值校验,仅在J完全空闲时才会走首次分配J的分支,判断顺序不合理;且在任务可同时被C、J分配的场景下,代码固定优先分配给C,没有优先分配给更早空闲的执行方,极端重叠场景下可能错误判定任务无法分配。
  • 缺少输出结果校验:代码遍历完所有任务后,没有检查分配数组中是否仍存在未填充的空位,直接拼接字符串返回。一旦出现索引匹配错位、漏分配任务的情况,输出结果会直接不符合格式要求。
  • 时间复杂度隐患:依赖list.index()的匹配方式会产生O(n²)的时间开销,当测试用例的任务规模较大时,容易出现运行超时的问题。
优化方向
  • 排序时同步记录每个任务的原始索引:把任务整理为(开始时间, 结束时间, 原始索引)的元组再排序,遍历每个任务时可以直接拿到对应的原始位置填充分配结果,不需要靠值匹配查找索引,彻底避免重复值带来的匹配错误。
  • 调整资源分配逻辑:遍历排序后的任务时,分别比较当前任务的开始时间与C、J的当前结束时间,优先把任务分配给更早空闲的执行方;如果两个执行方都无法容纳当前任务,再返回IMPOSSIBLE。
  • 增加最终校验环节:所有任务分配完成后,检查分配数组是否存在未填充的空位,存在则直接调整返回格式。

内容的提问来源于stack exchange,提问作者anu

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.01 06:24:04