"""Guided lab: a non-preemptive job queue and streaming waiting-time median."""

import heapq


class MedianTracker:
    def __init__(self):
        self.lower = []  # Negative values implement a max-heap.
        self.upper = []

    def add(self, value):
        if not self.lower or value <= -self.lower[0]:
            heapq.heappush(self.lower, -value)
        else:
            heapq.heappush(self.upper, value)
        if len(self.lower) > len(self.upper) + 1:
            heapq.heappush(self.upper, -heapq.heappop(self.lower))
        elif len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))
        if len(self.lower) == len(self.upper):
            return (-self.lower[0] + self.upper[0]) / 2
        return -self.lower[0]


def schedule_report(jobs):
    """jobs: (ID, arrival, duration); tie: duration, then lexical ID."""
    if any(arrival < 0 or duration <= 0 for _, arrival, duration in jobs):
        raise ValueError("Arrival must be nonnegative and duration positive")
    if len({job[0] for job in jobs}) != len(jobs):
        raise ValueError("Job IDs must be distinct")
    arrivals = sorted(jobs, key=lambda job: (job[1], job[0]))
    ready, records, medians = [], [], []
    tracker = MedianTracker()
    now = next_job = total_wait = 0
    while next_job < len(arrivals) or ready:
        if not ready and next_job < len(arrivals):
            now = max(now, arrivals[next_job][1])
        while next_job < len(arrivals) and arrivals[next_job][1] <= now:
            identity, arrival, duration = arrivals[next_job]
            heapq.heappush(ready, (duration, identity, arrival))
            next_job += 1
        duration, identity, arrival = heapq.heappop(ready)
        wait = now - arrival
        records.append({"id": identity, "start": now,
                        "finish": now + duration, "wait": wait})
        total_wait += wait
        medians.append(tracker.add(wait))
        now += duration
    return {"schedule": records, "total_wait": total_wait,
            "median_trace": medians,
            "median_wait": medians[-1] if medians else None,
            "finish": now}