759. Employee Free Time

Description

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.

Constraints

• 1 <= schedule.length , schedule[i].length <= 50

• 0 <= schedule[i].start < schedule[i].end <= 10^8

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : O(ClogC), where C is the number of intervals across all employees.
 * Space complexity : O(C)
 */

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> result = new ArrayList();
        List<Interval> intervals = new ArrayList();
        schedule.forEach(s -> intervals.addAll(s));
        
        Collections.sort(intervals, (i1, i2) -> i1.start-i2.start);
        Interval currMax = intervals.get(0);
        
        for(Interval curr: intervals) {
            if(currMax.end < curr.start) {
                result.add(new Interval(currMax.end, curr.start));
                currMax = curr;
            } else {
                currMax = (currMax.end < curr.end)? curr: currMax;
            }
        }
        return result;
    }
}

Follow up