TL;DR: The union, meaning any GPU idle, is the classic merge: sort by start, and extend the current interval whenever the next one starts at or before the current end. The intersection, meaning every GPU idle, is a sweep line: emit a plus-one event at each interval start and a minus-one at each end, sort, walk them keeping a running count, and record the spans where the count equals the number of GPUs. The trap is that a single GPU can report overlapping intervals, and each one contributes its own plus-one, so that GPU alone can push the counter to the threshold and the answer will include times when only one GPU was idle. The fix is one line: merge each GPU's own intervals before generating events. The other decision to make explicitly is whether touching intervals, where one ends exactly as the next begins, count as continuous, and the answer depends on whether the endpoints are inclusive, which is a question to ask rather than assume.
How to approach it
Do the union first because it is short and it establishes the sorting idea. Then the intersection as a sweep, and immediately name the double-counting trap, because it is the whole difficulty and an implementation that ignores it produces wrong answers that look right. State the touching-interval question as a question. Close with the tests, which are all boundary cases.
A strong answer
A typical situation: a capacity report says the fleet had two hours a day when every GPU was simultaneously idle, and a proposal to run batch work in those windows is built on it. The intervals came from a monitoring system that emits an interval per sample window, so consecutive samples produce adjacent and sometimes overlapping intervals for the same GPU, and the counter was reaching the threshold on one GPU's samples alone.
The union:
def merge(intervals):
"""Union: the times when at least one interval covers the point."""
if not intervals:
return []
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: []
Without the per-source merge, GPU 2's overlapping pair at (0,8) and (7,12) both contribute a plus-one, so between 7 and 8 the counter reads 4 rather than 3 on a three-GPU fleet. With a threshold of 3, that interval is emitted even when GPU 0 or GPU 1 is busy. The bug produces extra intervals rather than missing ones, so the result looks generous and plausible, which is why it survives review.
Interval Merging and Utilization Logs covers the wider pattern, including how allocation events become intervals in the first place.
The three decisions to make explicitly:
1. are endpoints inclusive?
with inclusive endpoints, [0,5] and [5,10] touch and should merge into [0,10]
with half-open [0,5) and [5,10), they are adjacent and merging them is still correct for
a union but the boundary handling differs
the code above uses <= in the merge and sorts starts before ends, which treats touching as
continuous. That is a choice, and it should be stated rather than discovered
2. what does a zero-length interval mean?
the intersection guard `t > start` drops them, which is right for "when was everything
idle" and wrong if a zero-length event is meaningful in the data model
3. what if a GPU has no intervals at all?
it was never idle, so the intersection is empty. The code gets this right because that GPU
contributes no events and the counter never reaches n. Worth a test, because an
implementation that iterates only over GPUs with events silently drops the constraint
Complexity and scale:
union O(m log m) for m intervals, dominated by the sort
intersection O(m log m) likewise, one sort of 2m events
memory O(m) for the events
at fleet scale
16,384 GPUs sampled every minute over a day = 16,384 x 1,440 = 23.6 million intervals
merging each GPU's own first reduces this substantially, since consecutive idle samples
collapse into one interval
if the raw stream is too large for memory, the same sweep works streaming, since events can
be produced in time order per source and merged with a heap
sanity: a day of per-minute samples across a large fleet is tens of millions of intervals,
which sorts in seconds and does not need anything cleverer than this
The reversal condition: the intersection over every GPU is rarely the question anyone actually wants. "When was the whole fleet idle" is almost never true on a busy cluster and is not useful when it is. The questions that get asked are "when were at least k GPUs idle", which is the same sweep with the threshold changed from n to k, and "how many GPU-hours were idle in total", which is a simpler sum over merged per-GPU intervals. Both fall out of the same code, and asking which one is wanted before writing is worth more than the implementation, which is the habit The Practical Coding Screen Playbook is built around.
What interviewers probe next
- "Change it to at least k idle." One character: compare the count against k rather than n. That generality is why the sweep is the right structure.
- "What if intervals arrive unsorted and streaming?" Sort per source, then merge the per-source event streams with a heap, which keeps memory bounded by the number of sources rather than by the number of intervals.
- "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; integers, typically epoch milliseconds, avoid it entirely.
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); 23.6 million intervals from a day of per-minute samples across 16,384 GPUs sorts in seconds.