LeetCode 759. Employee Free Time

Question

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]]

Constraints:

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

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

Solution

What we need to return is the common free times for all employees. Thus, the identity of employees does not matter. We can flatten schedule into a 1D list and sort it by start. Then we can solve this problem with the same idea as LeetCode 56. Merge Intervals.

class Interval {
    public int start;
    public int end;

    public Interval() {
    }

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
}

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    // contains all intervals
    List<Interval> timeline = new ArrayList<>();
    for (List<Interval> list : schedule) {
        timeline.addAll(list);
    }
    // sort by start in ascending order
    Collections.sort(timeline, new Comparator<Interval>() {
        @Override
        public int compare(Interval o1, Interval o2) {
            return o1.start - o2.start;
        }
    });
    int len = timeline.size();
    List<Interval> result = new ArrayList<>();
    if (len == 0) {
        return result;
    }
    int prevEnd = timeline.get(0).end;
    // each common interval is defined by the largest previous end and the smallest next start
    for (int i = 1; i < len; i++) {
        Interval curr = timeline.get(i);
        if (curr.start > prevEnd) { // no overlap
            result.add(new Interval(prevEnd, curr.start));
            prevEnd = curr.end;
        } else { // overlap
            prevEnd = Math.max(prevEnd, curr.end);
        }
    }
    return result;
}