Problem statement

https://leetcode.com/problems/employee-free-time/

Solution

Very similar to Problem 0056 Merge Intervals. One solution is just to sort all intervals and them go one by one with O(n log n) complexity, where n is total number of intervals.

There is improvement with O(n log k) complexity, where k is number of employees. Our schedules are already sorted, so we keep always not more than k elements in our heap, each time extract smallest and add next one from this employer if we have it. Then we compare if start < beg, where right is our moving pointer, the place we reached so far and beg is start of new interval. If it is true, we add new gap. In any case we update our right = max(right, end). In the end we need to deal with first interval which starts with minus infinity.

Complexity

Time complexity is O(n log k), space complexity is O(n).

Code

class Solution:
    def employeeFreeTime(self, S):
        res, pq = [], []
        k, right = len(S), -float("inf")
        for i in range(k):
            heappush(pq, (S[i][0].start, S[i][0].end, i, 0))

        while pq:
            beg, end, ix, iy = heappop(pq)
            if right < beg:
                res.append([right, beg])

            right = max(right, end)
            if iy < len(S[ix]) - 1:
                heappush(pq, (S[ix][iy+1].start, S[ix][iy+1].end, ix, iy+1))

        return [Interval(a, b) for a, b in res[1:]]