Given per-GPU idle intervals, compute when any GPU was idle and when every GPU was idle. Write both.

TL;DR: Merge all intervals to find when any GPU was idle. To find when every GPU was idle, first merge each GPU's own intervals, then sweep their start and end events while counting active GPUs; otherwise overlapping reports from one device can be counted as several devices.

How to approach it

Agree on the observation window and interval boundaries, then implement the union as a sort followed by a scan. Reuse that operation to remove overlap within each GPU's reports before computing the intersection. Test an empty source, adjacent intervals and duplicated reports from one device.

A strong answer

Suppose you want to find a window for maintenance when every GPU is idle. The monitoring system can report overlapping intervals for the same device. Counting those reports directly makes one device contribute twice, so the result may include time when another device was busy. The sweep must count distinct idle GPUs, which is why each source is merged first.

The union:

def merge(intervals):
    """Union: the times when at least one interval covers the point."""
    intervals = list(intervals)
    if not intervals:
        return []
    if any(s >= e for s, e in intervals):
        raise ValueError("intervals must have positive duration")
    xs = sorted(intervals)                 # by start, then end
    out = [list(xs[0])]
    for s, e in xs[1:]:
        if s <= out[-1][1]:                # <= treats touching as continuous
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return [tuple(x) for x in out]

The intersection:

def intersect_all(per_gpu):
    """Times when EVERY GPU is idle. per_gpu is a list of interval lists, one per GPU."""
    n = len(per_gpu)
    if n == 0:
        return []
    events = []
    for gpu in per_gpu:
        for s, e in merge(gpu):            # <- merge each GPU first, or it double-counts
            events.append((s, 1))
            events.append((e, -1))
    events.sort(key=lambda x: (x[0], -x[1]))   # at equal time, starts before ends
    out, active, start = [], 0, None
    for t, d in events:
        prev = active
        active += d
        if prev < n <= active:             # count reached all GPUs
            start = t
        elif prev >= n > active:           # count dropped below
            if start is not None and t > start:
                out.append((start, t))
            start = None
    return out

Running both on a three-GPU example with a deliberate overlap inside one GPU:

per-GPU idle
  GPU 0: [(0, 10), (20, 30)]
  GPU 1: [(5, 25)]
  GPU 2: [(0, 8), (7, 12), (22, 40)]     <- overlapping intervals from one source

GPU 2's own intervals merge first: [(0, 12), (22, 40)]
ANY idle (union):        [(0, 40)]
ALL idle (intersection): [(5, 10), (22, 25)]

checking by hand
  [0,10] and [5,25] and [0,12]  ->  [5,10]
  [20,30] and [5,25] and [22,40] ->  [22,25]
touching intervals [(0,5),(5,10)] merge to: [(0, 10)]
one GPU with no idle intervals at all:      []

The three-GPU example has four active interval reports between 7 and 8, although only three devices exist. It illustrates the inflated count, but all three GPUs really are idle then. To expose a false positive, use GPU 0 intervals (0, 10) and (1, 9), with GPU 1 idle only during (20, 30). Without merging GPU 0 first, a threshold of two reports incorrectly emits (1, 9) even though GPU 1 is busy throughout.

Interval Merging and Utilization Logs covers the wider pattern, including how allocation events become intervals in the first place.

Count idle GPUs, not overlapping reports

Merge each GPU’s own intervals before intersecting the sources.

1. Normalize each GPU’s intervals

   Merge overlapping and adjacent spans so one GPU contributes at most one active interval.

2. Sort endpoint events

   Emit +1 at a start and −1 at an end; use the implementation’s defined tie ordering.

3. Sweep the active count

   Open a candidate span when the count reaches the number of required GPUs.

4. Close when the count falls below the target

   Emit only a span with positive duration.

Use half-open intervals [start, end) for this example. Adjacent idle intervals can merge into one continuous span. The input validator rejects zero or negative duration; the intersection also omits zero-duration contacts between different sources. Point events would need a different result type.

An empty source means that GPU was never idle only when monitoring coverage is complete. Missing coverage is unknown. Keep every required GPU in the input, including those with no intervals, so the function cannot silently drop a constraint.

Both operations take O(m log m) time for m input intervals because sorting dominates. The intersection stores O(m) endpoint events. At 16,384 GPUs with 1,440 intervals each, the input contains 23,592,960 intervals before merging. That count warrants a memory measurement on the actual representation.

Merging each source first can reduce the event count when reports overlap or are adjacent. For data too large to sort in memory, externally sort it or merge already ordered streams with a heap. Arbitrarily late events need an explicit lateness policy; a heap alone cannot repair unordered input with bounded memory.

Check what the maintenance decision actually needs. If any group of k idle GPUs is sufficient, use that threshold instead of requiring the whole fleet to be idle. If the question is total idle GPU-hours, sum each GPU's merged intervals. These are different quantities: the duration of their union does not count how many GPUs were idle together.

What interviewers probe next

• "Change it to at least k idle." Use k in both threshold transitions and validate 1 <= k <= the number of GPUs. That generality is why the sweep is the right structure.
• "What if intervals arrive unsorted and streaming?" Use external sorting or a defined lateness bound first. A heap merges already ordered streams; it cannot make arbitrarily late events correct with fixed memory.
• "How do you handle open-ended intervals?" A GPU idle at the end of the window has no end event; substitute the window's end so the sweep terminates, and document that the last interval is truncated.
• "What about float timestamps?" Comparisons are exact enough for ordering, but equality at boundaries becomes fragile; integer timestamps avoid floating-point equality problems, but the chosen resolution still limits what the logs distinguish.

Common mistakes

• Not merging each source's intervals first, which double-counts and produces extra intersections that look plausible.
• Sorting ends before starts at equal times, which closes an interval a moment before reopening it and produces spurious splits.
• Ignoring GPUs with no intervals, which drops a constraint and over-reports.
• Assuming touching intervals should or should not merge without asking which the data model means.

Key takeaways

• Union: sort by start and extend while the next start is at or before the current end.
• Intersection: sweep plus-one and minus-one events with a counter, and record spans where the count equals the number of sources.
• Merge each source's own intervals before generating events, or one source's overlapping samples reach the threshold alone.
• Both are O(m log m); 16,384 GPUs with 1,440 intervals each produce 23,592,960 intervals before merging.