from heapq import *

#class Interval:
#    def __init__(self, start, end):
#        self.start = start
#        self.end = end

class EmployeeInterval:

    def __init__(self, interval, employeeIndex, intervalIndex):
        self.interval = interval  # interval representing employee's working hours
        # index of the list containing working hours of this employee
        self.employeeIndex = employeeIndex
        self.intervalIndex = intervalIndex  # index of the interval in the employee list

    def __lt__(self, other):
        # min heap based on meeting.end
        return self.interval.start < other.interval.start

class Solution:
  def findEmployeeFreeTime(self, schedule):
    
    def overlap(a, b):
      if a and b:
        return b.start <= a.end 
      return False

    def merge(a, b):
      return Interval(min(a.start, b.start), max(a.end, b.end))

    result = []

    # insert the employee first intervals 
    min_heap = [EmployeeInterval(sched[0], index, 0) for index, sched in enumerate(schedule)]
    heapify(min_heap)
    
   
    prev_interval = None
    
    while min_heap:
      emp = heappop(min_heap)
      
      # if previous interval overlaps with the current interval
      if overlap(prev_interval, emp.interval):
        # merge the intervals and store it
        prev_interval = merge(emp.interval, prev_interval)
      else:
        
        # if no overlapping
        if prev_interval:
          # append a new interval that consist of the previous interval end new interval start [gap]
          result.append(Interval(prev_interval.end, emp.interval.start))
        prev_interval = emp.interval
      
      # if employee has more intervals add it to the heap 
      if emp.intervalIndex + 1 < len(schedule[emp.employeeIndex]):
        new_interval = schedule[emp.employeeIndex][emp.intervalIndex + 1]
        new_emp = EmployeeInterval(new_interval, emp.employeeIndex, emp.intervalIndex + 1)
        heappush(min_heap, new_emp)

    return result