Merge overlapping weekly time 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)
• <Day> is one of Mon, Tue, Wed, Thu, Fri, Sat, Sun
• Examples: "Mon 9:00", "Mon 13:00", "Tue 09:30"

Example input:

[["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)$).

Merge Overlapping Weekly Time 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]).

Hints

1. 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.
2. 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).
3. 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.