#!/usr/bin/python
# -*- coding: utf-8 -*-
"""A sample problem from YouTube video "Google Coding Interview With A College Student."

It sounded trivial but it took me 11 minutes and 32 lines of code.
This version takes linearithmic time; a version that takes linear time
if the inputs are presorted (or if a linear-time sort is available) is
feasible.  (At 6'42" in the video it is explained that they are
sorted.)

My version also is incorrect if there are meetings in the input that
begin before the person's start time, though this is stipulated to not
happen, and I totally neglected the constraint to filter out blocks
that are shorter than some limit (you can convert to absolute minutes
with lambda t: t // 100 * 60 + t % 100 and then subtract and filter.)
And also I forgot to add 'open' events at the beginning of the day.
These are easily fixed but are not in the 11 minutes!

Perhaps more seriously, this solution only works reliably because
'open' comes alphabetically after 'closed'!

After thinking about it for a bit I wrote calendarprob2.py.

In the video, the explanation of the problem ended at 5'38" and the
guy starts writing code around 28'.

"""

def bothopen(person1, person2):
    p1times, (p1min, p1max) = person1
    p2times, (p2min, p2max) = person2
    start = max(p1min, p2min)
    end = min(p1max, p2max)
    events = sorted([(a, 'p1closed') for a, b in p1times] +
                    [(b, 'p1open') for a, b in p1times] +
                    [(a, 'p2closed') for a, b in p2times] +
                    [(b, 'p2open') for a, b in p2times] +
                    [(end, 'p1closed'), (end, 'p2closed')])

    results = []

    p1 = 'closed', None
    p2 = 'closed', None
    for time, event in events:
        if time < start or time > end:
            continue

        if event == 'p1open':
            p1 = 'open', time
        elif event == 'p2open':
            p2 = 'open', time
        elif event == 'p1closed':
            if p1[0] == p2[0] == 'open':
                results.append((max(p1[1], p2[1]), time))
            p1 = 'closed'
        elif event == 'p2closed':
            if p1[0] == p2[0] == 'open':
                results.append((max(p1[1], p2[1]), time))
            p2 = 'closed'

    return results

if __name__ == '__main__':
    print(bothopen(([(900, 1030), (1200, 1300), (1600, 1800)], (900, 2000)),
                   ([(1000, 1130), (1230, 1430), (1430, 1500), (1600, 1700)], (1000, 1830))))