Implement Interval Overrides and Top-K Strings

Problem Statement

You are monitoring compute resources where tasks or configurations are assigned to time windows. Each assignment specifies a half-open time interval [start, end) and an associated string label.

Assignments arrive sequentially. When a new interval is added, it overrides any existing intervals (or parts of intervals) that it overlaps with. Existing intervals may be completely replaced, clipped at the ends, or split into two disconnected segments.

Implement the function top_k_interval_labels(intervals: list[tuple[int, int, str]], k: int) -> list[str] which:

1. Applies the list of intervals sequentially, allowing later intervals to override earlier ones.
2. Computes the total non-overlapping duration assigned to each unique label across the final timeline.
3. Returns the top k labels with the greatest total duration, ordered from highest duration to lowest. If two labels have identical duration, tie-break alphabetically in ascending order ('a' before 'b').

If there are fewer than k unique labels with duration greater than 0, return all of them in the specified order.

Function Signature

def top_k_interval_labels(intervals: list[tuple[int, int, str]], k: int) -> list[str]:
    pass

Examples

Example 1

Input:
intervals = [
    (0, 10, "alpha"),
    (5, 8, "beta"),
    (2, 6, "gamma")
]
k = 2

Output: ["alpha", "gamma"]

Explanation:
- Initially: [0, 10) is "alpha" (duration 10).
- After (5, 8, "beta"): [0, 5) is "alpha", [5, 8) is "beta", [8, 10) is "alpha".
- After (2, 6, "gamma"): "gamma" overrides [2, 6).
  Timeline becomes:
  - [0, 2): "alpha" (duration 2)
  - [2, 6): "gamma" (duration 4)
  - [6, 8): "beta" (duration 2)
  - [8, 10): "alpha" (duration 2)

Final durations:
- "alpha": 2 + 2 = 4
- "gamma": 4
- "beta": 2

Both "alpha" and "gamma" have duration 4. Due to lexicographical tie-break, "alpha" comes before "gamma". The top 2 are ["alpha", "gamma"].

Example 2

Input:
intervals = [
    (1, 5, "A"),
    (0, 10, "B")
]
k = 1

Output: ["B"]

Explanation:
Interval (0, 10, "B") completely covers (1, 5, "A"). Final durations are "B": 10, "A": 0. The top 1 is ["B"].

Constraints

• 0 <= len(intervals) <= 2000
• 0 <= start < end <= 10^9
• 1 <= len(label) <= 30 (lowercase and uppercase ASCII characters)
• 1 <= k <= 1000

Edge Cases

• An interval completely enclosing or wiping out previous intervals.
• An override splitting an existing interval into two.
• Labels with 0 final duration should not be included in the output.
• k greater than the number of surviving labels.