759. Employee Free Time - Detailed Explanation

Problem Statement

In this problem, you are given the working schedules of several employees. Each employee's schedule is represented as a list of non-overlapping intervals sorted by start time. An interval is defined by a start time and an end time. The goal is to determine the common free time intervals across all employees—that is, the time slots when every employee is available (i.e., none of them are working).

For example, if one employee is busy during [1, 3] and [6, 7] and another is busy during [2, 4] and [9, 12], you must find the intervals where there is no overlap with any working time. Note that the free time intervals should be finite, and you should not consider the time before the first work interval or after the last work interval.

Examples

Example 1

• Input:
  • Employee 1: [1, 3], [6, 7]
  • Employee 2: [2, 4]
  • Employee 3: [2, 5], [9, 12]
• Output:
  • [5, 6], [7, 9]
• Explanation:
  • First, merge all the working intervals from every employee. When merged, the intervals become [1, 5], [6, 7], and [9, 12].
  • The gaps between these merged intervals are [5, 6] and [7, 9], which represent the common free time.

Example 2

• Input:
  • Employee 1: [1, 2], [5, 6]
  • Employee 2: [1, 3]
  • Employee 3: [4, 10]
• Output:
  • [3, 4]
• Explanation:
  • The merged working intervals are [1, 3] and [4, 10].
  • The gap between these intervals is [3, 4], which is the common free time.

Constraints

• Each employee’s schedule is a list of non-overlapping intervals sorted by start time.
• The free time intervals must be finite intervals (do not consider free time before the first working interval or after the last working interval).

Hints

1. Flatten and Merge:

   • Think about how you would merge overlapping intervals from multiple lists. Once merged, the gaps between these intervals are the free times.

2. Sorting:

   • Since the individual schedules are already sorted, you can flatten all intervals into one list and then sort this combined list based on start times.

3. Finding Gaps:

   • After merging overlapping intervals, the free time is simply the gap between the end of one interval and the start of the next interval.

Approach 1: Merge All Intervals

Step-by-Step Explanation

1. Flatten the Schedules:

   • Combine all intervals from each employee into one list.

2. Sort the Intervals:

   • Sort the flattened list of intervals by their start times.

3. Merge Overlapping Intervals:

   • Iterate through the sorted list and merge intervals that overlap or touch.
   • For each interval, if its start time is less than or equal to the end time of the previous merged interval, update the end time of the merged interval to the maximum of both end times. Otherwise, add the current interval as a new merged interval.

4. Identify Free Time:

   • Once you have a list of merged intervals that represent the overall working times, iterate through these merged intervals.
   • For any two consecutive intervals, the gap between the end of the first and the start of the second interval is a free time interval.

5. Return the Free Intervals:

   • Collect and return all these gaps as the result.

Visual Walkthrough (Using Example 1)

• Step 1: Flatten:

  • Employee 1: [1, 3], [6, 7]
  • Employee 2: [2, 4]
  • Employee 3: [2, 5], [9, 12]
  • Flattened list: [1, 3], [6, 7], [2, 4], [2, 5], [9, 12]

• Step 2: Sort:

  • Sorted list: [1, 3], [2, 4], [2, 5], [6, 7], [9, 12]

• Step 3: Merge:

  • Start with [1, 3].
  • [2, 4] overlaps with [1, 3] → merge to [1, 4].
  • [2, 5] overlaps with [1, 4] → merge to [1, 5].
  • [6, 7] does not overlap with [1, 5] → new merged interval.
  • [9, 12] does not overlap with [6, 7] → new merged interval.
  • Merged intervals: [1, 5], [6, 7], [9, 12].

• Step 4: Find Gaps:

  • Gap between [1, 5] and [6, 7]: [5, 6].
  • Gap between [6, 7] and [9, 12]: [7, 9].

• Result:

  • The common free time intervals are [5, 6] and [7, 9].

Approach 2: K-Way Merge with a Min-Heap

Explanation

1. Initialize a Min-Heap:

   • Since each employee’s schedule is individually sorted, you can use a min-heap to merge them in a manner similar to merging k sorted lists.

2. Extract the Minimum Interval:

   • Insert the first interval from each employee’s schedule into the min-heap, sorted by start time.

   • Repeatedly extract the interval with the smallest start time and add the next interval from that employee’s schedule to the heap.

3. Merge While Extracting:

   • As you extract intervals, merge overlapping intervals on the fly and record gaps when you detect a non-overlap.

4. Result:

   • The recorded gaps are the common free times.

Note

• Although the heap approach is effective when you want to avoid flattening the entire list at once, the merging approach (flatten, sort, then merge) is simpler and more intuitive in this case.

Complexity Analysis

• Time Complexity:

  • Flattening and sorting the intervals takes O(N log N) time, where N is the total number of intervals across all employees.

  • Merging the intervals is O(N).

  • Overall, the time complexity is O(N log N).

• Space Complexity:

  • O(N) space is required to store the flattened list of intervals and the merged intervals.

Python Code