Suppose we want to build a scheduling app. We have the times people are currently busy, e.g.

{

Alice: [(13.5, 14), (15.75, 17)],

Bob: [(9, 12), (13, 14), (14, 16)],

Eve: [(9, 11), (12.5, 13.5), (14, 15), (16, 18)]

Mallory: [(0, 9), (12, 24)]

}

For simplicity, lets represent times as numbers between 0 and 24 and the times people are busy as (start_time, end_time) pairs. For example, (13.5, 14) means that Alice is busy from 1:30PM-2PM.

Given a list of people's schedules, write a function to return a list of the time intervals all the people in the list are free to meet.

Method 1 Nlog(N) time, O(N) space. N is the total number of (start_time, endtime) pairs.

• Group all intervals into a list, sort it by the start_time in ascending order.
• Create an unavailable list to merge intervals together.
• Create an available list to store the gaps between the intervals.

def blend(dic):
    schedules = []
    for lst in dic.values():
        schedules.extend(lst)
    schedules.sort()
    unavailable = [schedules[0]]
    for i in xrange(1, len(schedules)):
        if unavailable[-1][1] < schedules[i][0]:
            unavailable.append(schedules[i])
        elif unavailable[-1][1] < schedules[i][1]:
            unavailable[-1][1] = schedules[i][1]

    available = []
    if unavailable[0][0] != 0:
        available.append((0, unavailable[0][0]))
    for i in xrange(1, len(unavailable)):
        available.append((unavailable[i-1][1], unavailable[i][0]))
    if available[-1][1] != 24:
        available.append((unavailable[-1][1], 24))
    return available