Employee Free Time

HardProblemExternal linkUpdated Oct 25, 2026

Description

You get every employee's working schedule: for each person, a sorted list of the intervals when they're busy, with no overlaps. Return the free time that all of them share: the intervals when nobody is busy, sorted.

Only finite intervals of positive length count. There's no free time before the first busy interval or after the last one, and none at a single moment where one interval ends as another starts.

Examples

Example 1

Input: schedule = [[[1, 2], [5, 6]], [[1, 3]], [[4, 10]]]

Output: [[3, 4]]

Explanation: Somebody is busy at every moment from 1 to 3 and from 4 to 10, so only 3 to 4 is free for all three.

Example 2

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

Output: [[5, 6], [7, 9]]

Explanation: Merged, the busy time is 1 to 5, 6 to 7 and 9 to 12, which leaves 5 to 6 and 7 to 9.

Constraints

1 ≤ schedule.length ≤ 50
1 ≤ schedule[i].length ≤ 50
0 ≤ start < end ≤ 10^8 for every interval
Each employee's intervals are sorted, and each ends before the next one starts

Editorial

Brute Force

Intuition

Cut the day at every start and every end. Between two neighbouring cut points, either somebody is busy the whole time, or nobody is busy at all, because no interval starts or ends inside the piece. So check each piece against every interval. The free pieces can't meet each other: the point between two pieces is somebody's start or end, so that person is busy on one side of it.

Step-by-Step Explanation

Let's take three people, A [[1, 4], [10, 12]], B [[2, 5], [13, 14]] and C [[7, 8]]:

From 1 to 2, A is busy the whole time, with [1, 4].
From 2 to 4, A is busy the whole time, with [1, 4].
From 4 to 5, B is busy the whole time, with [2, 5].
From 5 to 7, nobody is busy. That's free time.
From 7 to 8, C is busy the whole time, with [7, 8].
From 8 to 10, nobody is busy. That's free time.
From 10 to 12, A is busy the whole time, with [10, 12].
From 12 to 13, nobody is busy. That's free time.
From 13 to 14, B is busy the whole time, with [13, 14].
Every piece checked, 31 interval checks in all. The free time is [[5, 7], [8, 10], [12, 13]].

Cut at Every Endpoint — Each row is one busy interval, named by its person. The shaded band is the piece being checked; the amber interval covers it. The chips are the free time found.

Algorithm

Collect every start and end, sorted, without repeats.
For each two neighbouring points p and q, look for an interval with start ≤ p and q ≤ end.
If there's none, [p, q] is free time.

Code

class Solution {
public:
    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
        vector<vector<int>> busy;
        for (const auto& person : schedule) busy.insert(busy.end(), person.begin(), person.end());
        vector<int> points;                                  // every start and end, once each
        for (const auto& iv : busy) { points.push_back(iv[0]); points.push_back(iv[1]); }
        sort(points.begin(), points.end());
        points.erase(unique(points.begin(), points.end()), points.end());
        vector<vector<int>> free;
        for (size_t k = 0; k + 1 < points.size(); k++) {
            int p = points[k], q = points[k + 1];
            bool covered = false;                            // is somebody busy for all of p to q?
            for (const auto& iv : busy)
                if (iv[0] <= p && q <= iv[1]) { covered = true; break; }
            if (!covered) free.push_back({p, q});
        }
        return free;
    }
};

class Solution:
    def employeeFreeTime(self, schedule: list[list[list[int]]]) -> list[list[int]]:
        busy = [iv for person in schedule for iv in person]
        points = sorted({x for iv in busy for x in iv})     # every start and end, once each
        free = []
        for p, q in zip(points, points[1:]):
            if not any(s <= p and q <= e for s, e in busy):     # nobody is busy anywhere from p to q
                free.append([p, q])
        return free

class Solution {
    public int[][] employeeFreeTime(int[][][] schedule) {
        List<int[]> busy = new ArrayList<>();
        for (int[][] person : schedule) busy.addAll(Arrays.asList(person));
        TreeSet<Integer> set = new TreeSet<>();              // every start and end, once each
        for (int[] iv : busy) { set.add(iv[0]); set.add(iv[1]); }
        Integer[] points = set.toArray(new Integer[0]);
        List<int[]> free = new ArrayList<>();
        for (int k = 0; k + 1 < points.length; k++) {
            int p = points[k], q = points[k + 1];
            boolean covered = false;                         // is somebody busy for all of p to q?
            for (int[] iv : busy)
                if (iv[0] <= p && q <= iv[1]) { covered = true; break; }
            if (!covered) free.add(new int[]{p, q});
        }
        return free.toArray(new int[0][]);
    }
}

var employeeFreeTime = function(schedule) {
    const busy = schedule.flat();
    const points = [...new Set(busy.flat())].sort((a, b) => a - b);   // every start and end, once each
    const free = [];
    for (let k = 0; k + 1 < points.length; k++) {
        const p = points[k], q = points[k + 1];
        if (!busy.some(([s, e]) => s <= p && q <= e)) free.push([p, q]);   // nobody is busy from p to q
    }
    return free;
};

Complexity Analysis

Time Complexity: O(N²)

For N intervals there are up to 2N − 1 pieces, each checked against up to N intervals.

Space Complexity: O(N)

The points.

Why This Approach Is Not Efficient

Every piece is checked against the intervals one by one: 31 checks for these 5 intervals, and up to about 12.5 million for 50 people with 50 intervals each. That still passes here, but it grows with the square of N. All it's really asking is when the busy time stops, and a sort answers that for every piece at once.

Optimal Approach - Merge Everyone's Busy Time

Intuition

Free for everyone means nobody is busy, so it doesn't matter who is busy, only when. Put everyone's intervals in one list, sorted by start, and walk it keeping end, the latest moment somebody is busy so far. That's the merge from Introduction to Intervals, without writing the merges down.

When the next interval starts after end, nobody is busy from end to its start: that's free time. Starting exactly at end leaves no gap, since a single moment has no length. Then end becomes the larger of the two ends, because an interval that starts later can still end sooner.

Step-by-Step Explanation

Let's take the same three people:

Everyone's intervals together, sorted by start. The first one, [1, 4], means somebody is busy until 4.
B [2, 5] starts at 2, before the busy stretch ends at 4, so there's no gap. The busy stretch now runs until 5.
C [7, 8] starts at 7, after everyone is free from 5, so [5, 7] is free time. Now somebody is busy until 8.
A [10, 12] starts at 10, after everyone is free from 8, so [8, 10] is free time. Now somebody is busy until 12.
B [13, 14] starts at 13, after everyone is free from 12, so [12, 13] is free time. Now somebody is busy until 14.
One pass after the sort. The free time is [[5, 7], [8, 10], [12, 13]].

Busy Until, Then Free — Everyone's intervals sorted by start. The amber line is how long somebody is busy so far; a shaded band is free time found.

Algorithm

Put every interval in one list and sort it by start.
Set end to the first interval's end.
For each next interval: if its start is greater than end, add [end, start]. Then set end to the larger of end and its end.

Code

class Solution {
public:
    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
        vector<vector<int>> busy;
        for (const auto& person : schedule) busy.insert(busy.end(), person.begin(), person.end());
        sort(busy.begin(), busy.end());                          // everyone's busy time, by start
        vector<vector<int>> free;
        int end = busy[0][1];                                    // the latest busy moment so far
        for (size_t k = 1; k < busy.size(); k++) {
            if (busy[k][0] > end) free.push_back({end, busy[k][0]});   // nobody is busy between end and start
            end = max(end, busy[k][1]);
        }
        return free;
    }
};

class Solution:
    def employeeFreeTime(self, schedule: list[list[list[int]]]) -> list[list[int]]:
        busy = sorted(iv for person in schedule for iv in person)   # everyone's busy time, by start
        free, end = [], busy[0][1]                  # end: the latest busy moment so far
        for start, finish in busy[1:]:
            if start > end:                         # nobody is busy between end and start
                free.append([end, start])
            end = max(end, finish)
        return free

class Solution {
    public int[][] employeeFreeTime(int[][][] schedule) {
        List<int[]> busy = new ArrayList<>();
        for (int[][] person : schedule) busy.addAll(Arrays.asList(person));
        busy.sort((a, b) -> Integer.compare(a[0], b[0]));         // everyone's busy time, by start
        List<int[]> free = new ArrayList<>();
        int end = busy.get(0)[1];                                // the latest busy moment so far
        for (int k = 1; k < busy.size(); k++) {
            int start = busy.get(k)[0], finish = busy.get(k)[1];
            if (start > end) free.add(new int[]{end, start});    // nobody is busy between end and start
            end = Math.max(end, finish);
        }
        return free.toArray(new int[0][]);
    }
}

var employeeFreeTime = function(schedule) {
    const busy = schedule.flat().sort((a, b) => a[0] - b[0]);   // everyone's busy time, by start
    const free = [];
    let end = busy[0][1];                            // the latest busy moment so far
    for (let k = 1; k < busy.length; k++) {
        const [start, finish] = busy[k];
        if (start > end) free.push([end, start]);    // nobody is busy between end and start
        end = Math.max(end, finish);
    }
    return free;
};

Complexity Analysis

Time Complexity: O(N log N)

The sort, then one pass. Each person's list is already sorted, so a heap that always takes the earliest next interval from the k lists makes it O(N log k).

Space Complexity: O(N)

The combined list.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Keeping the last interval's end. end = finish

On schedule = [[[1, 10]], [[2, 3]], [[5, 6]]] it returns [[3,5]]; the answer is []. Sorted by start, a later interval can end earlier: [2, 3] after [1, 10]. The busy time runs to the largest end so far, so keep the max.

Reporting touching as free time. if start >= end:

On schedule = [[[1, 3]], [[3, 5]]] it returns [[3,3]]; the answer is []. When one interval ends exactly as the next starts, there's no free moment between them: [3, 3] has no length. A gap needs start > end.

Finding each person's gaps. free.append([person[k][1], person[k + 1][0]])

On schedule = [[[1, 2], [5, 6]], [[2, 5]]] it returns [[2,5]]; the answer is []. A gap in one person's day isn't free time if someone else is busy then. Free time has to be free for everyone, so merge all the busy time first.

Skipping the sort. busy = [iv for person in schedule for iv in person]

On schedule = [[[8, 9]], [[1, 2]], [[4, 5]]] it returns []; the answer is [[2,4],[5,8]]. Each person's list is sorted, but one person after another isn't: the second person's day can start before the first one's ends. Sort everyone's intervals together.

Where This Pattern Is Taught

Merging and the gaps between merges are taught in Introduction to Intervals, along with why touching intervals leave no free time.