Google Code Jam 2008 Qualification Round B

(後で書く)

UPPER_BOUND = 10000 
num_test = int(fi.readline())
for test_id in range(num_test):

    tatime = int(fi.readline())
    na, nb = map(int, fi.readline().split())
    event_table = []
    # event_table (time, arrive/depart as -1/+1, A/B as 0/1)
    # order and depart==+1 is important to handle synchronous events
    #print "a to b"
    for i in range(na):
        line = fi.readline().split()
        #print line
        dept, arrv = map(toMin, line)
        event_table.append((dept, +1, 0))
        event_table.append((arrv + tatime, -1, 1))

    #print "b to a"
    for i in range(nb):
        line = fi.readline().split()
        #print line
        dept, arrv = map(toMin, line)
        event_table.append((dept, +1, 1))
        event_table.append((arrv + tatime, -1, 0))

    event_table.sort()
    result = [0, 0]
    trains = [0, 0]
    for (t, diff, pos) in event_table:
        #print (t, diff, pos), trains, result
        trains[pos] -= diff
        if trains[pos] < 0:
            trains[pos] += 1
            result[pos] += 1

    p("Case #%d: %d %d" % (test_id + 1, result[0], result[1]))