谷歌密码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 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))

Answer 1

您实施了一种蛮力方法来解决它。您的代码运行缓慢，时间复杂度 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))

我希望您找到这些信息，并帮助您理解并保持努力工作。