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
相关产品推荐
相关产品推荐

