Merge Overlapping Time Intervals Given as Parallel Start and End Lists

You receive time intervals as two lists of equal length: `starts[i]` and `ends[i]` are the start time and end time of interval `i`, and the intervals are in no particular order. Merge every group of overlapping intervals into a single interval and return the resulting intervals, none of which overlap. The report describes the task as merging intervals whose times overlap; this version also merges intervals that only touch at an endpoint and fixes the output order, as stated in Rules below. ### Function Signature ```python def merge_time_intervals(starts: list[int], ends: list[int]) -> list[list[int]]: ``` ### Rules - Interval `i` covers every time `t` with `starts[i] <= t <= ends[i]`. - Two intervals overlap when they share at least one time, so `[1, 5]` and `[5, 7]` overlap. Overlap chains: if A overlaps B and B overlaps C, all three belong to the same group even when A and C do not overlap. - Each output interval `[s, e]` covers exactly one maximal group: `s` is the smallest start and `e` the largest end in the group. - Return the output intervals as `[start, end]` pairs sorted by start in ascending order. Because the output intervals are disjoint, this order is unique. ### Constraints - `1 <= len(starts) == len(ends) <= 10^5` - `0 <= starts[i] <= ends[i] <= 10^9` - Intervals may repeat or contain one another. ### Examples **Example 1** ```text Input: starts = [1, 8, 2, 15], ends = [3, 10, 6, 18] Output: [[1, 6], [8, 10], [15, 18]] ``` `[1, 3]` and `[2, 6]` overlap and become `[1, 6]`; `[8, 10]` and `[15, 18]` overlap nothing. **Example 2** ```text Input: starts = [5, 1], ends = [7, 5] Output: [[1, 7]] ``` `[1, 5]` and `[5, 7]` touch at time 5, so they are merged. **Example 3** ```text Input: starts = [9, 1, 2], ends = [9, 10, 3] Output: [[1, 10]] ``` `[2, 3]` and the single point `[9, 9]` both lie inside `[1, 10]`.