Merge a Staff Roster Into Time Segments Listing Who Is On Duty

You are given a staff roster in which each entry names one person and the time span of their shift. Merge the roster into a single timeline: cut the time from the earliest shift start to the latest shift end into consecutive segments at every shift start and every shift end, and report, for each segment, its start time, its end time and everyone on duty during it. A segment in which nobody is on duty is reported too, with an empty list. The candidate's report gives one input and its expected output; the rules below make the interval convention, the empty segments and the order of names within a segment exact. ### Function Signature ```python def merge_roster(roster: list[list[str | int]]) -> list[list[int | list[str]]]: ``` ### Rules - Each roster entry is `[name, start, end]`, and that person is on duty during the half-open interval `[start, end)`. A shift that ends at time `t` and a shift that starts at time `t` do not overlap. - Let `t0 < t1 < ... < tm` be all the distinct `start` and `end` values in the roster, sorted ascending. The output contains exactly one segment `[t_i, t_(i+1), names]` for each consecutive pair, in ascending time order. It therefore begins at the earliest start and ends at the latest end, with no segment outside that span. - `names` lists every person whose shift covers the segment, in the order their entries appear in `roster` (not alphabetically and not by start time). It is an empty list when nobody is on duty. - The roster is not necessarily sorted. ### Constraints - `1 <= len(roster) <= 1000` - `0 <= start < end <= 10^9` - Each name is 1 to 20 English letters, and no name appears in more than one entry. - The output has at most `2 * len(roster) - 1` segments. ### Examples **Example 1** ```text Input: roster = [["Mary", 10, 40], ["John", 30, 50], ["Peter", 50, 80], ["Crystal", 100, 150], ["Jane", 120, 180]] Output: [[10, 30, ["Mary"]], [30, 40, ["Mary", "John"]], [40, 50, ["John"]], [50, 80, ["Peter"]], [80, 100, []], [100, 120, ["Crystal"]], [120, 150, ["Crystal", "Jane"]], [150, 180, ["Jane"]]] ``` The distinct times are 10, 30, 40, 50, 80, 100, 120, 150 and 180. John's shift ends at 50 exactly when Peter's begins, so they never share a segment. Nobody is on duty from 80 to 100, which gives the segment with an empty list. **Example 2** ```text Input: roster = [["Ann", 5, 20], ["Bob", 0, 10], ["Cid", 8, 12]] Output: [[0, 5, ["Bob"]], [5, 8, ["Ann", "Bob"]], [8, 10, ["Ann", "Bob", "Cid"]], [10, 12, ["Ann", "Cid"]], [12, 20, ["Ann"]]] ``` The distinct times are 0, 5, 8, 10, 12 and 20. Ann is listed before Bob in every segment they share because her entry comes first in `roster`, even though Bob's shift starts earlier. **Example 3** ```text Input: roster = [["Zoe", 3, 7]] Output: [[3, 7, ["Zoe"]]] ```