Merge Weekly Time Intervals
Company: Nextdoor
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `merge_weekly_intervals(intervals)`.
Each interval is `[start_day, start_time, end_day, end_time]`. Days are `Mon`, `Tue`, `Wed`, `Thu`, `Fri`, `Sat`, or `Sun`. Times use 24-hour `HH:MM`. Intervals are closed, never wrap from Sunday into the next week, and satisfy start at or before end.
Return merged intervals in the same representation, sorted by start. Intervals that overlap or share an endpoint must merge.
### Constraints
- `0 <= len(intervals) <= 200000`
- Times range from `00:00` through `23:59`.
- Input may be unsorted and contain duplicates.
### Example
`[["Mon","09:00","Mon","17:00"], ["Mon","17:00","Tue","10:00"], ["Wed","12:00","Wed","13:00"]]` returns `[["Mon","09:00","Tue","10:00"], ["Wed","12:00","Wed","13:00"]]`.
```hint Normalize before merging
Convert each day and time to an integer minute offset from Monday, then apply the closed-interval merge rule.
```
```hint Format only after the algorithm
Keeping parsing and formatting separate from interval logic makes boundary tests easier.
```
Quick Answer: Implement `merge_weekly_intervals(intervals)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Each interval is `[start_day, start_time, end_day, end_time]` within one Monday-to-Sunday week. Days use three-letter names and times use 24-hour `HH:MM`. Return the same representation sorted by start after merging closed intervals that overlap or share an endpoint. Intervals never wrap into the next week.
Constraints
- 0 <= len(intervals) <= 200000.
- Days are Mon through Sun and times range from 00:00 through 23:59 in HH:MM format.
- Every interval stays within one week and has start at or before end.
- Intervals are closed; input may be unsorted or duplicated and must not be mutated.
Examples
Input: ([],)
Expected Output: []
Explanation: Empty input returns no intervals.
Input: ([['Mon', '09:00', 'Mon', '09:00']],)
Expected Output: [['Mon', '09:00', 'Mon', '09:00']]
Explanation: A zero-length singleton interval is preserved.
Hints
- Test empty, singleton, duplicate, contained, and unsorted intervals.
- Include intervals sharing an endpoint both within one day and across a day boundary.
- Exercise Monday 00:00, Sunday 23:59, a zero-length interval, and a one-minute gap.