Merge overlapping weekly time intervals
Company: Nextdoor
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of time intervals representing meetings. Each interval is a pair of strings in the format:
- `"<Day> <H>:<MM>"` (24-hour time)
- `<Day>` is one of `Mon, Tue, Wed, Thu, Fri, Sat, Sun`
- Examples: `"Mon 9:00"`, `"Mon 13:00"`, `"Tue 09:30"`
Example input:
```text
[["Mon 9:00", "Mon 13:00"], ["Mon 11:00", "Mon 16:00"]]
```
Two intervals overlap if they occur on the same day and their time ranges intersect (endpoints may be treated as overlapping, i.e., `[9:00, 13:00]` overlaps `[13:00, 14:00]`).
Task:
1. Parse the strings into comparable time values.
2. Merge all overlapping intervals (per day) and return the merged list.
Output requirements:
- Return intervals in the same string format.
- Sort output by day-of-week (Mon→Sun), then by start time.
Clarify/assume:
- All intervals start < end.
- Intervals may span different days, but each individual interval’s start and end are on the same day.
- Input size can be large enough that an efficient solution is expected (better than \(O(n^2)\)).
Quick Answer: This question evaluates the ability to parse weekday and 24-hour time strings, reason about interval overlap, and apply efficient merging and sorting techniques for time-based intervals.