from heapq import *
def main():
    schedules = [
       [(10, 29), (50, 99), (120, 200)],
       [(25, 90), (130, 190)],
       [(13, 20), (30, 90), (120, 180)],
    ]


main()

def findFree(schedules):
    h = []
    res = []
    for i in range(len(schedules)):
        heappush(h, (schedules[i][0][0], schedules[i][0][1], i, 0))

    while(h):
        print(h)
        (start, end, person, index) = heappop(h)
        if(h):
            (nextStart, nextEnd, nextPerson, nextIndex) = heappop(h)
            if(end < nextStart):
                res.append([(end, nextStart)])
            else:
                if(nextIndex != len(schedules[nextPerson]) - 1):
                    for i in range(nextIndex, len(schedules[nextPerson])):
                        if(schedules[nextPerson][i][0] > end):
                            break
                    heappush(h, (schedules[nextPerson][i][0], schedules[nextPerson][i][1], nextPerson, i))
        else:
            res.append([schedules[person][index - 1][1], start])
        if(index + 1 < len(schedules[person])):
                heappush(h, (schedules[person][index + 1][0], schedules[person][index + 1][1], person, index + 1))

    return res

print findFree([
       [(10, 29), (50, 99), (120, 200)],
       [(25, 90), (130, 190)],
       [(13, 20), (30, 90), (120, 180)],
    ])


def findOrder(strings):
    nextDict = {}
    countDict = {}
    res = []

    # initialize dict
    for string in strings:
        for char in string:
            nextDict[char] = []
            countDict[char] = 0

    # build graph
    for i in range(len(strings) - 1):
        j = 0
        fst = strings[i]
        snd = strings[i + 1]
        while(j < len(fst) and j < len(snd)):
            if(fst[j] != snd[j]):
                nextDict[fst[j]].append(snd[j])
                countDict[snd[j]] += 1
                break
            j += 1

    # generate topo sort
    while(nextDict):
        for (k, v) in nextDict.iteritems():
            if(countDict[k] == 0):
                res.append(k)
                for node in v:
                    countDict[node] -= 1

        for toDel in res:
            if(toDel in nextDict):
                nextDict.pop(toDel, None)
    return res

print(findOrder(['xa', 'xp', 'xc', 'pr']))