Bird
Raised Fist0
Interview PrepintervalshardFacebookAmazonGoogle

Employee Free Time

Choose your preparation mode4 modes available
</>
IDE
def employeeFreeTime(schedule: list[list[list[int]]]) -> list[list[int]]:public List<List<Integer>> employeeFreeTime(List<List<List<Integer>>> schedule)vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>> &schedule)function employeeFreeTime(schedule)
def employeeFreeTime(schedule):
    # Write your solution here
    pass
class Solution {
    public List<List<Integer>> employeeFreeTime(List<List<List<Integer>>> schedule) {
        // Write your solution here
        return new ArrayList<>();
    }
}
#include <vector>
using namespace std;

vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>> &schedule) {
    // Write your solution here
    return {};
}
function employeeFreeTime(schedule) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: [[2,3]]Returning gaps inside busy intervals due to incorrect merging.✅ Sort all intervals and merge overlapping or touching intervals before finding gaps.
Wrong: [[2,2]]Including zero-length intervals as free time.✅ Filter out intervals where start == end before returning.
Wrong: [[3,4],[5,6]]Treating touching intervals as free time gaps.✅ Merge touching intervals as continuous busy time, no gaps between [1,2] and [2,3].
Wrong: [[1,10]]Returning entire timeline as free time when employees have no intervals.✅ Return empty list if no finite free intervals exist; infinite free time not representable.
Wrong: [[3,4],[7,8]]Greedy approach missing intervals causing false free time.✅ Merge all intervals from all employees before detecting gaps.
✓
Test Cases
t1_01basic
Input[[[1,2],[5,6]],[[1,3]],[[4,10]]]
Expected[[3,4]]

Merging all intervals gives [1,3], [4,10], [5,6] merged into [1,3] and [4,10]. The gap between 3 and 4 is free time for all employees.

t1_02basic
Input[[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Expected[[5,6],[7,9]]

Merged intervals are [1,5], [6,7], [9,12]. Free times are [5,6] and [7,9].

t2_01edge
Input[]
Expected[]

No employees means no busy intervals, so no finite free intervals to return.

t2_02edge
Input[[[1,5]]]
Expected[]

Only one employee with one interval means no common free time inside that interval; outside is infinite and not returned.

t2_03edge
Input[[[1,2],[2,3]],[[2,3],[3,4]]]
Expected[]

Intervals that touch but do not overlap produce no free time between them.

t2_04edge
Input[[],[],[]]
Expected[]

Employees with no intervals means entire timeline is free but infinite intervals are not returned.

t3_01corner
Input[[[1,10]],[[2,3],[4,5],[6,7],[8,9]],[[1,2],[3,4],[5,6],[7,8],[9,10]]]
Expected[]

All employees' intervals cover the entire range [1,10] without gaps, so no free time.

t3_02corner
Input[[[1,3],[5,7]],[[2,4],[6,8]],[[1,2],[4,5],[7,9]]]
Expected[]

Intervals merge to [1,4],[5,9]. The gaps at 4 and 9 are zero length, so no free time intervals of positive length exist; output is empty.

t3_03corner
Input[[[1,2],[5,6]],[[1,3]],[[4,10]]]
Expected[[3,4]]

This test checks that the solution does not confuse 0/1 knapsack style inclusion with interval merging; intervals must be merged by timeline, not by employee.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

Input with 100000 intervals tests O(N log N) sweep line approach; brute force O(N*M*T) will TLE.

Practice

(1/5)
1. Consider the following Python code implementing the optimal approach for maintaining disjoint intervals. After executing addNum(1), addNum(3), and addNum(2) in order, what is the final state of self.intervals?
easy
A. [[1, 1], [3, 3]]
B. [[1, 1], [2, 3]]
C. [[1, 2], [3, 3]]
D. [[1, 3]]

Solution

  1. Step 1: Trace addNum(1)

    Intervals empty, append [1,1]. Intervals = [[1,1]]
  2. Step 2: Trace addNum(3) and addNum(2)

    addNum(3): bisect_left finds i=1, no merges, insert [3,3]. Intervals = [[1,1],[3,3]]. addNum(2): bisect_left finds i=1, left_merge true (1's end +1 == 2), right_merge true (3's start -1 == 2), merge intervals[0] and intervals[1] into [1,3], pop intervals[1]. Intervals = [[1,3]]
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Intervals correctly merged into one [OK]
Hint: Merging occurs when val bridges two intervals [OK]
Common Mistakes:
  • Forgetting to merge both sides
  • Inserting duplicates
  • Off-by-one errors in merging
2. What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?
medium
A. O(n) because intervals need to be scanned linearly for merging
B. O(log n) due to binary search and limited merging operations
C. O(n log n) because each insertion requires sorting intervals
D. O(1) since insertion is always at the end or start

Solution

  1. Step 1: Identify main operations in addNum

    addNum uses binary search (bisect_left) to find insertion index in O(log n).
  2. Step 2: Analyze merging cost

    Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search dominates, merges are constant time [OK]
Hint: Binary search + constant merges -> O(log n) [OK]
Common Mistakes:
  • Assuming linear scan for merging
  • Confusing sorting cost per insertion
  • Ignoring constant merge steps
3. The following code attempts to add a number to the intervals but contains a subtle bug. Which line causes incorrect behavior when adding a number already covered by an existing interval?
medium
A. Missing lines checking if val is already covered by existing intervals
B. Line calculating i = bisect_left(intervals, [val, val])
C. Line checking if intervals is empty and appending [val, val]
D. Line popping intervals[i] after merging two intervals

Solution

  1. Step 1: Identify missing coverage check

    The code lacks checks to return early if val is already inside intervals[i-1] or intervals[i].
  2. Step 2: Consequence of missing check

    Without this, duplicates or incorrect merges occur, corrupting intervals.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing coverage check causes incorrect behavior [OK]
Hint: Always check if val is already covered before inserting [OK]
Common Mistakes:
  • Forgetting coverage check
  • Incorrect merge boundaries
  • Popping wrong interval
4. What is the time complexity of the optimal two pointers approach for finding the intersection of two interval lists, each of length m and n respectively?
medium
A. O(max(m, n) * log(min(m, n))) due to sorting or binary search steps.
B. O(m * n), since each interval in one list is compared to all intervals in the other list.
C. O(m + n), because each pointer advances at most m or n times through the lists.
D. O(m + n + k), where k is the number of intersections found.

Solution

  1. Step 1: Identify pointer movements

    Each pointer i and j moves forward only, never backward, up to m and n times respectively.
  2. Step 2: Sum pointer advances

    Total steps ≤ m + n, so time complexity is O(m + n).
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Two pointers scan each list once without nested loops [OK]
Hint: Two pointers each advance linearly, no nested iteration [OK]
Common Mistakes:
  • Confusing with brute force O(m*n)
  • Assuming sorting is needed
  • Including output size k in complexity incorrectly
5. Suppose intervals can be reused multiple times (i.e., you can merge overlapping intervals repeatedly, possibly reusing intervals). Which modification to the merge intervals algorithm correctly handles this scenario?
hard
A. Use the same sorting + one pass merge approach; repeated intervals will be merged naturally.
B. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes.
C. Use a brute force nested loop approach to merge intervals until no overlaps remain.
D. Use a graph-based approach to find connected components of overlapping intervals and merge each component.

Solution

  1. Step 1: Understand that reusing intervals means overlaps can form complex connected groups.

    Simple one-pass merge assumes intervals appear once and sorted order suffices.
  2. Step 2: Recognize that overlapping intervals form connected components in a graph.

    Building a graph where intervals are nodes and edges represent overlaps allows merging all connected intervals correctly.
  3. Step 3: Evaluate options.

    Use the same sorting + one pass merge approach; repeated intervals will be merged naturally. fails because one pass merge assumes no reuse. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes. is inefficient and may not terminate quickly. Use a brute force nested loop approach to merge intervals until no overlaps remain. is brute force and inefficient. Use a graph-based approach to find connected components of overlapping intervals and merge each component. correctly models the problem and merges all connected intervals.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Graph connected components capture all overlapping intervals including reuse. [OK]
Hint: Model reuse as graph connected components [OK]
Common Mistakes:
  • Assuming one pass merge works with reuse
  • Using repeated merges without termination guarantee
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard