Employee free time: common free intervals across schedules

You get every person's busy times for one day. Each person's list is sorted and has no overlaps. Return the intervals within the day when nobody is busy.

Interface

Unless you agree on a different interface with the interviewer, assume:

• common_free_time(schedules: list[list[list[int]]], day_start: int, day_end: int) -> list[list[int]] — schedules[i] holds person i's busy intervals as [start, end). Returns the free intervals [start, end) inside [day_start, day_end), sorted, positive length only, with adjacent free time merged.

Example

common_free_time([[[60, 120]], [[30, 90], [150, 180]]], 0, 240)
    ->  [[0, 30], [120, 150], [180, 240]]

common_free_time([[], []], 0, 10)
    ->  [[0, 10]]                         # nobody is busy

common_free_time([[[0, 30], [200, 240]], [[20, 60]], [[100, 130]]], 0, 240)
    ->  [[60, 100], [130, 200]]

Constraints

• Up to 10^4 people and 10^5 intervals in total.
• Busy intervals are half-open, so [30, 60) and [60, 90) touch but leave no gap.
• Times are integers (for example, minutes in a day).

Clarifying questions

• Are the day bounds given, or should I return only the gaps between busy times?
• Are intervals half-open or closed? Is a zero-length gap returned?
• Can a busy interval extend outside the day?
• Should the output be in the same interval format as the input?

What a strong answer covers

• Merge all busy intervals: sort them all (O(N log N)), or k-way merge the per-person lists with a heap (O(N log k)), using the fact that each list is already sorted.
• One pass over the merged intervals that emits each gap, clipped to the day.
• Edge cases: nobody busy, busy all day, intervals that touch, intervals outside the day bounds.
• Tests that check sortedness and positive length.

Follow-ups

• No day bounds: return only the finite gaps between busy times.
• Return only free slots of at least d minutes, or the first such slot.
• Find times when at least m of the n people are free.
• The calendars change all the time. How do you answer "when are these people free?" quickly?