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.
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), where `<Day>` is one of `Mon, Tue, Wed, Thu, Fri, Sat, Sun` (e.g. `"Mon 9:00"`, `"Mon 13:00"`, `"Tue 09:30"`).
Two intervals overlap if they occur on the same day and their time ranges intersect. Endpoints are treated as overlapping, i.e. `[9:00, 13:00]` overlaps `[13:00, 14:00]`.
Parse the strings into comparable time values, merge all overlapping intervals (per day), and return the merged list.
Output requirements:
- Return intervals in the same string format `"<Day> <H>:<MM>"`, with the hour unpadded and the minute zero-padded to two digits (e.g. `"Mon 9:00"`, `"Tue 9:30"`).
- Sort the output by day-of-week (Mon -> Sun), then by start time.
Assumptions:
- Every interval has start < end.
- Each individual interval's start and end are on the same day.
- The input can be large, so an efficient (better than O(n^2)) solution is expected.
Constraints
- 0 <= number of intervals <= 10^5
- Each interval is a pair of strings in the format "<Day> <H>:<MM>" (24-hour).
- <Day> is one of Mon, Tue, Wed, Thu, Fri, Sat, Sun.
- For every interval, start < end and both endpoints are on the same day.
- Touching endpoints count as overlapping (e.g. [9:00,13:00] overlaps [13:00,14:00]).
Examples
Input: ([['Mon 9:00', 'Mon 13:00'], ['Mon 11:00', 'Mon 16:00']],)
Expected Output: [['Mon 9:00', 'Mon 16:00']]
Explanation: The two Monday intervals overlap (11:00 falls inside [9:00,13:00]), so they merge into one spanning [9:00,16:00].
Input: ([['Mon 9:00', 'Mon 13:00'], ['Mon 13:00', 'Mon 14:00']],)
Expected Output: [['Mon 9:00', 'Mon 14:00']]
Explanation: Touching endpoints are treated as overlapping, so [9:00,13:00] and [13:00,14:00] merge into [9:00,14:00].
Hints
- Convert each timestamp to an absolute comparable value: day index (Mon=0 .. Sun=6) plus minutes-since-midnight (h*60+m). This lets you sort and compare intervals numerically.
- Sort all intervals by (day, start). After sorting, a simple linear sweep merges overlaps: keep extending the current merged interval while the next interval is on the same day and its start is <= the current end (use <= so touching endpoints merge).
- When formatting back to strings, the hour is unpadded but the minute must be zero-padded to two digits, e.g. 9*60+5 -> "9:05". Sorting first guarantees the Mon->Sun, then start-time output order.