https://leetcode.com/problems/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.
(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.
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]]
- Merge Interval
class Solution(object):
def employeeFreeTime(self, schedule):
"""
:type schedule: List[List[Interval]]
:rtype: List[Interval]
"""
results = []
schedules = []
for times in schedule:
schedules.extend(times)
schedules.sort(key=lambda x: x.start)
pre = schedules[0]
for cur in schedules[1:]:
if cur.start > pre.end:
results.append(Interval(pre.end, cur.start))
pre = cur
else:
pre.start = min(pre.start, cur.start)
pre.end = max(pre.end, cur.end)
return results- MinHeap
"""
# Definition for an Interval.
class Interval(object):
def __init__(self, start=None, end=None):
self.start = start
self.end = end
"""
from heapq import *
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(object):
def employeeFreeTime(self, schedule):
"""
:type schedule: [[Interval]]
:rtype: [Interval]
"""
if schedule is None:
return []
n = len(schedule)
result, minHeap = [], []
# insert the first interval of each employee to the queue
for i in range(n):
heappush(minHeap, EmployeeInterval(schedule[i][0], i, 0))
previousInterval = minHeap[0].interval
while minHeap:
queueTop = heappop(minHeap)
# if previousInterval is not overlapping with the next interval, insert a free interval
if previousInterval.end < queueTop.interval.start:
result.append(Interval(previousInterval.end,
queueTop.interval.start))
previousInterval = queueTop.interval
else:
# overlapping intervals, update the prev if needed
if previousInterval.end < queueTop.interval.end:
previousInterval = queueTop.interval
# if there are more intervals available for the same employee, add their next interval
employeeSchedule = schedule[queueTop.employeeIndex]
if len(employeeSchedule) > queueTop.intervalIndex + 1:
heappush(minHeap, EmployeeInterval(employeeSchedule[queueTop.intervalIndex + 1],
queueTop.employeeIndex,
queueTop.intervalIndex + 1))
return result