# 759. Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)
Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

# Solution

Approach 1: for each slot, generate +1 for start, and -1 for end; sort and go over them to get periods of 0s.

# Code (Python)

Approach 1: (not verified on leetcode)

def all_free(meeting_schedules):
   avail = []
   max_time = 0
   for schedule in meeting_schedules:
       for meeting in schedule:
           avail.append((meeting[0], 1))
           avail.append((meeting[1], -1))
           max_time = max(max_time, meeting[1])
   avail.sort() # can be optimized to merged sorted (deep) lists
   result = []
   num_meetings = 0
   for time, delta in avail:
       before = num_meetings
       num_meetings += delta
       if num_meetings == 0:
           result.append([time])
       elif before == 0 and len(result) > 0:
           result[-1].append(time)
   if len(result[-1]) == 1:
       result[-1].append(max_time)
   return result[:-1] if result[-1][0] == result[-1][1] else result
 
def free_k(meeting_schedules, k): # k: k or more employees are free
   avail = []
   max_time = 0
   for schedule in meeting_schedules:
       for meeting in schedule:
           avail.append((meeting[0], 1))
           avail.append((meeting[1], -1))
           max_time = max(max_time, meeting[1])
   avail.sort() # can be optimized to merged sorted (deep) lists
   result = []
   num_meetings = 0
   for time, delta in avail:
       before = num_meetings
       num_meetings += delta
       print(before, num_meetings)
       if before == len(meeting_schedules) - k + 1 and num_meetings == len(meeting_schedules) - k:
           result.append([time])
       elif before == len(meeting_schedules) - k and num_meetings == len(meeting_schedules) - k + 1 and len(result) > 0:
           result[-1].append(time)
   if len(result[-1]) == 1:
       result[-1].append(max_time)
   return result[:-1] if result[-1][0] == result[-1][1] else result
 
schedule = [[[1,3], [6,7]], [[2,4]], [[2,3], [9,12]]]
print(all_free(schedule)) # [[4,6], [7,9]]
print(free_k(schedule, 2)) # [[3, 12]]

# Code (C++)

Approach 1:

Approach 2: