759. Employee Free Time

Problem Explanation:

Given a list of employee work schedules with each employee having a list of non-overlapping intervals representing their working hours, we are tasked with finding the common free time for all employees, or in other words, the times when all employees are not working.

The input is a nested list of intervals, each interval as [start, end], with start < end. The intervals are non-overlapping and are already sorted in ascending order. The output should also be a list of sorted intervals.

For example, consider schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]. Here, Employee 1 works from 1 to 3 and 6 to 7. Employee 2 works from 2 to 4 and Employee 3 works from 2 to 5 and 9 to 12. The common free time for all employees is [5,6] and [7,9] as these are the intervals when all employees are free.

Solution Approach:

The proposed solution concatenates all work schedules into a single list, sorts this list and then identifies the gaps between work intervals, which represent the common free time for all employees.

First, the solution creates an empty array to store the result. Then, it goes through the work shifts of each employee and combines all the intervals to a single list.

Next, this combined list of work intervals is sorted using the start of the work intervals. This will ensure that the work schedules are in chronological order.

After that, the solution stores the end time of the first shift in a variable called prevEnd, and then iterates through each work interval.

If the start of a work interval is greater than prevEnd, this means there's a gap between the end of the previous work shift and the start of the current work shift. This gap represents a common free time, which is then added to the result list.

Finally, prevEnd is updated with the maximum end time of the current work interval or the prevEnd.

Through this approach, the algorithm successfully identifies the common free time of all employees.

Python Solution

1
2python
3# Definition for an Interval.
4# class Interval:
5#     def __init__(self, start: int = None, end: int = None):
6#         self.start = start
7#         self.end = end
8
9class Solution:
10    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
11        # Flattening the schedule
12        intervals = [interval for employee in schedule for interval in employee]
13        # Sorting by start of each Interval
14        intervals.sort(key=lambda x: x.start)
15        res, end = [], intervals[0].end
16        # Checking for free time between intervals
17        for i in intervals[1:]:
18            if end < i.start:
19                res.append(Interval(end, i.start))
20            end = max(end, i.end)
21        return res

JavaScript Solution:

1
2javascript
3function Interval(start, end) {
4    this.start = start;
5    this.end = end;
6}
7
8function employeeFreeTime(schedule) {
9    // Flattening the schedule
10    let intervals = [].concat(...schedule);
11    // Sorting by start of each Interval
12    intervals.sort((a, b) => a.start - b.start);
13    let res = [], end = intervals[0].end;
14    // Checking for free time between intervals
15    for (let i = 1; i < intervals.length; i++) {
16        if (end < intervals[i].start) {
17            res.push(new Interval(end, intervals[i].start));
18        }
19        end = Math.max(end, intervals[i].end);
20    }
21    return res;
22}

Java Solution:

1
2java
3/**
4 * Definition for an interval.
5 * public class Interval {
6 *     int start;
7 *     int end;
8 *     Interval() { start = 0; end = 0; }
9 *     Interval(int s, int e) { start = s; end = e; }
10 * }
11 */
12public class Solution {
13    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
14        List<Interval> res = new ArrayList<>();
15        List<Interval> intervals = new ArrayList<>();
16        // Flattening the schedule
17        for (List<Interval> employee : schedule)
18            for (Interval interval : employee)
19                intervals.add(interval);
20        // Sorting by start of each Interval
21        Collections.sort(intervals, (a, b) -> a.start - b.start);
22        int end = intervals.get(0).end;
23        // Checking for free time between intervals
24        for (Interval interval : intervals) {
25            if (interval.start > end)
26                res.add(new Interval(end, interval.start));
27            end = Math.max(end, interval.end);
28        }
29        return res;
30    }
31}

These solutions work by first flattening the schedule list, then sorting the intervals by their start times. They then keep track of the end time of the current interval. If the start of the next interval is greater than this end time, it means there is a gap where all employees are free, and this gap is then added to the results. These solutions have a time complexity of O(N log N) due to the sorting operation, where N is the total number of intervals. The space complexity is also O(N) for storing the intervals and the result.

Solution Implementation