Consolidate On-Call Rotation Segments

Problem Statement

You are building a dashboard to visualize on-call coverage for an engineering team. The input is a list of on-call shifts, where each shift is defined by a start time, an end time, and an engineer's identifier.

Because multiple engineers can be on-call at the same time, shifts can overlap. You need to segment the overall timeline into contiguous, disjoint intervals [start, end) such that during each interval, the exact set of active engineers remains constant.

Write a function to consolidate these shifts into a sorted list of non-overlapping intervals, each accompanied by the lexicographically sorted list of active engineers.

Requirements

• Each output interval (start, end, engineers) represents a half-open interval [start, end) with start < end.
• engineers must be sorted in ascending lexicographical order and contain no duplicate IDs.
• Periods with no active engineers (gaps) must be omitted from the output.
• Adjacent intervals with the exact same set of active engineers must be merged into a single continuous interval.
• Output intervals must be sorted by start time in ascending order.

Interface

def consolidate_shifts(
    shifts: list[tuple[int, int, str]]
) -> list[tuple[int, int, list[str]]]:
    pass

Input & Output Format

• Input: shifts is a list of tuples (start, end, engineer_id), where start and end are integers, and engineer_id is a string.
• Output: A list of tuples (start, end, engineers), where start and end are integers, and engineers is a list[str].

Examples

Example 1

shifts = [
    (1, 5, "Alice"),
    (3, 7, "Bob")
]
# Output:
# [
#     (1, 3, ["Alice"]),
#     (3, 5, ["Alice", "Bob"]),
#     (5, 7, ["Bob"])
# ]

Explanation: From 1 to 3, only Alice is on duty. At time 3, Bob begins his shift, so both Alice and Bob are active until Alice's shift ends at 5. Bob continues alone until time 7.

Example 2

shifts = [
    (1, 4, "Alice"),
    (2, 4, "Bob"),
    (6, 8, "Alice")
]
# Output:
# [
#     (1, 2, ["Alice"]),
#     (2, 4, ["Alice", "Bob"]),
#     (6, 8, ["Alice"])
# ]

Explanation: Between 4 and 6, no engineer is on-call, so that interval is omitted.

Constraints

• 0 <= len(shifts) <= 2 * 10^4
• 0 <= start < end <= 10^9
• 1 <= len(engineer_id) <= 30, containing only alphanumeric characters.