# 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: