Employee Free Time - Practice Coding Problems

Employee Free Time - 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.

Note: 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.

Input & Output

Example 1 — Basic Case

$ Input: schedule = [[[1,3],[6,10]], [[2,4],[9,12]]]

› Output: [[4,6]]

💡 Note: Employee 1 works [1,3] and [6,10]. Employee 2 works [2,4] and [9,12]. Merging all intervals: [1,4] and [6,12]. The gap between them is [4,6].

Example 2 — Multiple Gaps

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

› Output: [[6,7]]

💡 Note: Employee 1: [1,3],[4,6]. Employee 2: [2,5],[7,9]. After merging: [1,6] and [7,9]. Free time is [6,7].

Example 3 — No Free Time

$ Input: schedule = [[[1,10]], [[2,6],[8,12]]]

› Output: []

💡 Note: Employee 1 works [1,10], Employee 2 works [2,6],[8,12]. Combined coverage is [1,12] with no gaps.

Constraints

1 ≤ schedule.length ≤ 50
1 ≤ schedule[i].length ≤ 50
schedule[i][j].length == 2
0 ≤ schedule[i][j][0] < schedule[i][j][1] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Multiple employee schedules with working intervals

Process

Merge all busy intervals to find covered time

Output

Gaps between merged intervals are free time

Key Takeaway

🎯 Key Insight: Free time is simply the gaps between merged busy intervals from all employees

Asked in

G Google 42 f Facebook 35 a Amazon 28 M Microsoft 25

The key insight is that free time equals gaps between merged busy intervals. Best approach is Sort and Merge: flatten all intervals, sort by start time, merge overlaps, then find gaps. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Time Points	O(n³)	O(n)	Check each possible time point against all employee schedules
Sort and Merge Intervals	O(n log n)	O(n)	Flatten all intervals, sort by start time, merge overlaps, find gaps
Priority Queue (Min-Heap)	O(n log n)	O(n)	Use min-heap to efficiently process intervals in chronological order

Brute Force - Check All Time Points — Algorithm Steps

Step 1: Collect all interval start and end points
Step 2: For each consecutive pair of points, check if all employees are free
Step 3: Add valid free intervals to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Points

Gather all start/end times from schedules

Check Intervals

For each time gap, verify no employee is working

Result

Return all free intervals found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int*** schedule, int* scheduleSizes, int** scheduleColSizes, int scheduleSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (scheduleSize == 0) {
        return NULL;
    }
    
    // Simplified implementation for C
    // This would require more complex parsing and memory management
    int** result = (int**)malloc(100 * sizeof(int*));
    *returnColumnSizes = (int*)malloc(100 * sizeof(int));
    
    // Basic implementation placeholder
    *returnSize = 0;
    return result;
}

int main() {
    // Complex input parsing would be needed for 3D array
    printf("[]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each pair of time points (O(n²)), we check all intervals (O(n))

⚠ Quadratic Growth

Space Complexity

O(n)

Store all boundary points and result intervals

⚡ Linearithmic Space

125.0K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Time Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler