谷歌密码2020年资格赛：问题3

Question

这是针对谷歌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 True

def 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))

Answer 1

您实施了一种蛮力方法来解决它。您的代码运行缓慢，时间复杂度 O（N^2），但您可以在 O（N*log（N）） 中执行此操作而不是检查 ，对数组进行排序并使用 C 或 J 的最后一个结束时间活动进行检查。（ 贪婪的方式解决它 ）notOverlap(activity, arr)在对数组进行排序之前，必须存储活动的索引。这是我的解决方案，但在阅读解决方案之前，请尝试自己实现它for testcasei in range(1, 1 + int(input())):&nbsp; &nbsp; n = int(input())&nbsp; &nbsp; acts = []&nbsp; &nbsp; for index in range(n):&nbsp; &nbsp; &nbsp; &nbsp; start, end = map(int, input().split())&nbsp; &nbsp; &nbsp; &nbsp; acts.append((start, end, index)) # store also the index&nbsp; &nbsp; acts.sort(reverse=True) # sort by starting time reversed&nbsp; &nbsp; # so the first activity go to the last&nbsp; &nbsp; d = ['']*n # construct the array for the answer&nbsp; &nbsp; cnow = jnow = 0 # next time C or J are available&nbsp; &nbsp; impossible = False # not impossible for now&nbsp; &nbsp; while acts: # while there is an activity&nbsp; &nbsp; &nbsp; &nbsp; start_time, end_time, index = acts.pop()&nbsp; &nbsp; &nbsp; &nbsp; if cnow <= start_time: # C is available to do the activity&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cnow = end_time&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; d[index] = 'C'&nbsp; &nbsp; &nbsp; &nbsp; elif jnow <= start_time:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; jnow = end_time&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; d[index] = 'J'&nbsp; &nbsp; &nbsp; &nbsp; else: # both are'nt available&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; impossible = True&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break&nbsp; &nbsp; if impossible:&nbsp; &nbsp; &nbsp; &nbsp; d = 'IMPOSSIBLE'&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; d = ''.join(d) # convert the array to string&nbsp; &nbsp; print("Case #%d: %s" % (testcasei, d))我希望您找到这些信息，并帮助您理解并保持努力工作。