Employee Free Time Python Solution with Tests

LeetCode 759, Hard. Topics: Array, Sorting, Sweep Line, Heap (Priority Queue). View on LeetCode. Generate this problem as a practice environment: tested reference solution, 13 parametrized pytest cases, and a playground notebook:

lcpy gen -n 759   # by problem number
lcpy gen -s employee_free_time   # by problem name

Problem

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 do not include intervals like [5, 5] in our answer, as they have zero length.

Examples

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 are not finite.

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints

1 <= schedule.length, schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n log n) where n is total number of intervals
    # Space: O(n)
    def employee_free_time(self, schedule: list[list[list[int]]]) -> list[list[int]]:
        # Flatten all intervals across employees, then merge overlapping ones.
        # Gaps between consecutive merged intervals are the common free time.
        intervals: list[list[int]] = [
            [start, end] for employee in schedule for start, end in employee
        ]
        intervals.sort()

        merged: list[list[int]] = []
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])

        free: list[list[int]] = []
        for i in range(1, len(merged)):
            if merged[i - 1][1] < merged[i][0]:
                free.append([merged[i - 1][1], merged[i][0]])
        return free

Complexity

Time	Space
O(n log n) where n is total number of intervals	O(n)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Employee Free Time Python Solution with Tests

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags