Google Codejam 2020资格赛：问题3

Question

这是谷歌2020年Codejam资格赛的第三个问题

评判系统说这个解决方案给出了一个错误的答案，但我不明白为什么。任何见解都将不胜感激

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））中完成它

不使用notOverlap(activity, arr)进行检查，对数组进行排序并使用上次结束时间活动C或J进行检查（贪婪的解决方法）

在对数组进行排序之前，必须存储活动索引

这是我的解决方案，但在阅读解决方案之前，请尝试自己实现它

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

我希望你能从中受益匪浅，帮助你理解，并继续努力工作