LC 0759 [H] Employee Free Time - ALawliet/algorithms GitHub Wiki
the naive solution re-sorts and is "merge sorted intervals" sorting for O(nlogn) [LC medium]
# O(nlogn)
class Solution:
def employeeFreeTime(self, schedule: 'list<list<Interval>>') -> 'list<Interval>':
intervals = sorted([i for s in schedule for i in s], key=lambda x: x.start)
res, end = [], intervals[0].end
for i in intervals[1:]:
if i.start > end:
res.append(Interval(end, i.start))
end = max(end, i.end)
return resbut the correct and optimized solution takes advantage of how the employee schedules are already sorted, so it's more like "merge k sorted" which uses heap for O(nlogk) [LC hard]
# O(nlogk)
"""
# Definition for an Interval.
class Interval:
def __init__(self, start: int = None, end: int = None):
self.start = start
self.end = end
"""
from queue import PriorityQueue
class Solution:
def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
min_heap = PriorityQueue()
res = []
for e in range(len(schedule)):
# queue the first interval for each employee in order from the front
min_heap.put( (schedule[e][0].start, schedule[e][0].end, e) )
schedule[e].pop(0)
end = min_heap.queue[0][1] # earliest interval by start, end, employee
while not min_heap.empty():
new_start, new_end, e = min_heap.get()
if new_start <= end:
# is overlapping = common time, extend it
end = max(end, new_end)
else: # (new_start > end), so (end, new_start)
# not common time, add it
res.append(Interval(end, new_start))
end = new_end # is set behind so we can look for next common time
# queue next employee interval
if schedule[e]:
min_heap.put( (schedule[e][0].start, schedule[e][0].end, e) )
schedule[e].pop(0)
return res