Time Segment: Merge and Query Overlapping Time Intervals to Find Free and Busy Windows

Question

## Problem

You are given a list of time intervals `[start, end]` (integers, minutes since midnight) representing busy periods. Implement:
- `merge() -> list[list[int]]` -- return merged non-overlapping busy intervals.
- `free_slots(day_start, day_end) -> list[list[int]]` -- return free windows within the working day.
- `is_free(start, end) -> bool` -- check if a proposed slot is entirely free.

```python
class Schedule:
    def __init__(self, intervals: list[list[int]]): ...
    def merge(self) -> list[list[int]]: ...
    def free_slots(self, day_start: int, day_end: int) -> list[list[int]]: ...
    def is_free(self, start: int, end: int) -> bool: ...
```

**Example:**
```
intervals = [[30,60],[20,50],[80,120]]
merge()          -> [[20,60],[80,120]]
free_slots(0,480)-> [[0,20],[60,80],[120,480]]
is_free(65,75)   -> True
```

## Follow-ups
1. A new meeting is added dynamically. How do you efficiently re-merge without re-sorting everything?
2. Multiple people's schedules need to be intersected. Find a slot where all are free for at least `duration` minutes.
3. How would you persist and query this schedule for millions of users?
4. Extend to recurring events (every Monday 9-10am). How do you expand them into concrete intervals on demand?

Time Segment: Merge and Query Overlapping Time Intervals to Find Free and Busy Windows

Question Details

Full Details

Topics

More from Square/Block