"""Guided lab: deduplicate incident tickets and prepare an investigation brief."""

from collections import Counter, deque
import heapq


def minimum_cover(tickets, required):
    """Shortest contiguous slice by ticket count; ties retain earliest slice."""
    required = set(required)
    if not required:
        return []
    counts, formed, left, best = Counter(), 0, 0, None
    for right, (_, _, category) in enumerate(tickets):
        if category in required:
            counts[category] += 1
            formed += counts[category] == 1
        while formed == len(required):
            if best is None or right - left < best[1] - best[0]:
                best = (left, right)
            outgoing = tickets[left][2]
            if outgoing in required:
                counts[outgoing] -= 1
                formed -= counts[outgoing] == 0
            left += 1
    if best is None:
        return None
    return [identity for identity, _, _ in tickets[best[0]:best[1] + 1]]


def incident_brief(events, window, k, required):
    """Event: (unique ticket ID, nondecreasing integer timestamp, category)."""
    if window <= 0 or k < 0:
        raise ValueError("Window must be positive and k nonnegative")
    if any(timestamp < 0 for _, timestamp, _ in events):
        raise ValueError("Timestamps must be nonnegative")
    if any(events[i][1] > events[i + 1][1] for i in range(len(events) - 1)):
        raise ValueError("Events must be in timestamp order")
    seen, accepted, active, counts = set(), [], deque(), Counter()
    duplicates = 0
    for identity, timestamp, category in events:
        # At timestamp t the active interval is (t-window, t].
        while active and active[0][1] <= timestamp - window:
            _, _, expired_category = active.popleft()
            counts[expired_category] -= 1
            if counts[expired_category] == 0:
                del counts[expired_category]
        if identity in seen:
            duplicates += 1
            continue
        seen.add(identity)
        ticket = (identity, timestamp, category)
        accepted.append(ticket)
        active.append(ticket)
        counts[category] += 1
    priority = [(-count, category) for category, count in counts.items()]
    heapq.heapify(priority)
    top = []
    for _ in range(min(k, len(priority))):
        negative_count, category = heapq.heappop(priority)
        top.append((category, -negative_count))
    return {"accepted": [ticket[0] for ticket in accepted],
            "duplicates": duplicates, "active_count": len(active), "top": top,
            "minimum_cover": minimum_cover(accepted, required)}