Problem

You’re building a real-time patient monitoring UI for a large hospital network. The backend emits vitals readings (heart rate, SpO₂, respiratory rate, etc.) from bedside devices. Due to Wi‑Fi jitter and device batching, events can arrive out of timestamp order, but the system guarantees a bounded lateness: an event’s timestamp will never be more than L seconds behind the maximum timestamp seen so far.

Rendering every raw event causes flicker and wasted work. The UI wants a clean stream of updates:

1. Bounded reordering: You may buffer events, but once a timestamp is “safe” (cannot be affected by future late arrivals), you must emit it.
2. Coalescing: For the same (timestamp, metric), only the last arriving value should be emitted (last-write-wins).
3. Deterministic ordering: Output must be sorted by increasing timestamp; for the same timestamp, emit metrics in lexicographic order.

Formal Task

Implement coalesce_vitals(events, L).

• Input:
  • events: list[tuple[int, str, int]] where each event is (t, metric, value)
  • L: non-negative integer lateness bound
• Output:
  • A list of coalesced events (t, metric, value) in the required order.

Flushing Rule

Let max_seen_t be the maximum timestamp observed so far while scanning events in arrival order. After processing each event, you must flush (emit) all buffered timestamps t such that:

• t <= max_seen_t - L

At end of stream, flush everything remaining.

Examples

Example 1

• Input: events = [(100,"HR",80), (90,"HR",78), (95,"SpO2",97), (100,"HR",81)], L = 5
• Output: [(90,"HR",78), (95,"SpO2",97), (100,"HR",81)]
• Explanation: When max_seen_t=100, cutoff is 95, so timestamps <=95 flush. At t=100, HR is overwritten to 81 before the final flush.

Example 2

• Input: events = [(5,"HR",70), (5,"HR",71), (5,"SpO2",98), (5,"SpO2",97)], L = 0
• Output: [(5,"HR",71), (5,"SpO2",97)]
• Explanation: With L=0, timestamp 5 is immediately flushable, but within that timestamp we still apply last-write-wins per metric.

Constraints

• 1 <= events.length <= 2 * 10^5
• 0 <= t <= 10^9
• 0 <= L <= 10^9
• 1 <= metric.length <= 10 (letters/digits/underscore)
• -10^6 <= value <= 10^6

Notes

• Multiple metrics can share the same timestamp.
• Many duplicates for the same (t, metric) may appear; only the last one (by arrival order) should be emitted.
• For the same timestamp, output metrics in lexicographic order (e.g., "HR" < "SpO2").