這是針對谷歌Codejam資格賽2020年第三個問題評審系統說這個解決方案給出了一個錯誤的答案，但我無法弄清楚為什么。任何見解將不勝感激。num_test_cases = int(input())def notOverlap(activity, arr): # returns true if we have no overlapping activity in arr for act in arr: if not (act[0] >= activity[1] or act[1] <= activity[0]): return False return Truedef decide(act, num_act): C, J = [], [] result = [None]*num_act for i in range(num_act): if notOverlap(act[i], C): C.append(act[i]) result[i] = "C" elif notOverlap(act[i], J): J.append(act[i]) result[i] = "J" else: return "IMPOSSIBLE" return "".join(result)for i in range(num_test_cases): num_act = int(input()) act = [] for _ in range(num_act): act.append(list(map(int, input().split()))) print("Case #" + str(i+1) + ": " + decide(act, num_act))
1 回答
慕俠2389804
TA貢獻1719條經驗 獲得超6個贊
您實施了一種蠻力方法來解決它。您的代碼運行緩慢，時間復雜度 O（N^2），但您可以在 O（N*log（N）） 中執行此操作
而不是檢查 ，對數組進行排序并使用 C 或 J 的最后一個結束時間活動進行檢查。（ 貪婪的方式解決它 ）notOverlap(activity, arr)
在對數組進行排序之前，必須存儲活動的索引。
這是我的解決方案，但在閱讀解決方案之前，請嘗試自己實現它
for testcasei in range(1, 1 + int(input())):
n = int(input())
acts = []
for index in range(n):
start, end = map(int, input().split())
acts.append((start, end, index)) # store also the index
acts.sort(reverse=True) # sort by starting time reversed
# so the first activity go to the last
d = ['']*n # construct the array for the answer
cnow = jnow = 0 # next time C or J are available
impossible = False # not impossible for now
while acts: # while there is an activity
start_time, end_time, index = acts.pop()
if cnow <= start_time: # C is available to do the activity
cnow = end_time
d[index] = 'C'
elif jnow <= start_time:
jnow = end_time
d[index] = 'J'
else: # both are'nt available
impossible = True
break
if impossible:
d = 'IMPOSSIBLE'
else:
d = ''.join(d) # convert the array to string
print("Case #%d: %s" % (testcasei, d))
我希望您找到這些信息，并幫助您理解并保持努力工作。
添加回答
舉報
0/150
提交
取消