Interval Coding Interview Questions: Boundary Rules, Sweeps, and Concurrent Events

Interval coding interview questions fail at the endpoints. If one meeting ends at 10:00 and another starts at 10:00, are they compatible? Under half-open [start,end) semantics they do not overlap; under closed [start,end] semantics they share an instant. State the contract before sorting. Every later comparison and sweep tie rule depends on it.

Use Merge Overlapping Intervals for the baseline sort-and-scan. The candidate-reported record supports that practice problem only. This guide adds shared-boundary truth tables, concurrent-event sweeps, deterministic payload rules, and calendar limitations.

Use Merge Overlapping Intervals as the closest PracHub drill while this guide develops the broader interview decision. PracHub question records are candidate-reported practice material: each record supports its own prompt, not a claim that every employer asks the same question.

Interval Coding Interview: Quick Answer

For valid half-open intervals with start < end, two intervals overlap when a.start < b.end and b.start < a.end. To merge, sort by start then end; merge when next.start < current.end, or use <= only if the product explicitly combines touching intervals. To count simultaneous activity, create (+1,start) and (-1,end) events and process ends before starts at the same time under half-open semantics.

Keep different outputs separate. Merging returns covered unions. Conflict detection can stop at the first overlap. Maximum concurrency tracks a running count and possibly the spans where the maximum holds. Scheduling rooms often uses a min-heap of end times. Zero-length intervals, invalid reversed endpoints, timezone conversion, and output ordering require explicit contracts.

Write an Endpoint Truth Table

With A=[1,3) and B=[3,5), A excludes 3 while B includes it, so there is no overlap. A=[1,4) and B=[3,5) overlap on [3,4). A=[1,5) contains B=[2,3). Duplicate intervals overlap completely. A zero-length [3,3) is empty under the mathematical convention, though an API may reject it.

Closed intervals use a.start <= b.end and b.start <= a.end; half-open uses strict comparisons. Do not mix a half-open overlap predicate with start-before-end sweep ordering, which behaves like closed boundaries at ties. If intervals carry integer points rather than continuous time, converting [l,r] to [l,r+1) can overflow at the maximum integer; use a wider type or retain explicit closed semantics.

Merge with a Named Touching Rule

def merge(intervals, merge_touching=False):
    ordered = sorted(intervals)
    out = []
    for start, end in ordered:
        if start >= end:
            raise ValueError("expected nonempty [start,end)")
        touches = start == out[-1][1] if out else False
        overlaps = bool(out) and start < out[-1][1]
        if overlaps or (merge_touching and touches):
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return [tuple(x) for x in out]

Sorting tuples supplies start then end order. Copy into new lists so the function does not mutate caller-owned intervals. Merging touching ranges is a presentation or storage policy, not the same as temporal overlap. [1,3) and [3,5) can be stored as [1,5) without claiming two meetings conflicted, but name that normalization separately.

Order Equal-Time Sweep Events Correctly

Encode each start as (time,+1) and end as (time,-1). Sorting the delta ascending processes -1 before +1 at equal times, matching half-open availability: a resource released at 10:00 can be reused immediately. For closed intervals, starts may need to count before ends. If you negate or customize event types, restate the actual order rather than relying on tuple magic.

To return maximum-concurrency spans, group all deltas at one timestamp. The count after applying time t describes the open span until the next distinct timestamp. Record [t,next_t) when that count equals the current maximum. Processing each tied event one by one can create transient counts at a zero-duration instant that do not correspond to a positive-length span.

Choose Scan, Heap, or Sweep from the Output

Merge and conflict detection use a sort-and-scan because only the current union end matters. Meeting-room allocation uses a min-heap keyed by the earliest room end: release all ends <= next.start under half-open semantics, then assign a room. Maximum simultaneous count uses event deltas or sorted starts and ends.

Returning which intervals conflict may require payload IDs and an active set, not only a count. Geometric line sweeps can use balanced trees because events change an ordered spatial set. Do not call every sorted endpoint solution “the sweep line” and ignore the active-state requirements. Complexity is usually O(n log n) for sorting plus output work; already sorted input can reduce it.

Preserve Deterministic Payload Semantics

Intervals often carry booking IDs, prices, or labels. When merging coverage, decide whether output keeps all contributing IDs, the first payload, a combined aggregate, or no payload. Python officially guarantees stable sorting, so equal-key records retain input order, but relying on that should be intentional and documented.

For room assignment, deterministic ties can use the smallest room ID after end time. For “most frequently used room,” a room reused at the same timestamp needs the same half-open release rule. If new meetings are delayed when all rooms are busy, preserve their duration and define whether ordering follows original start then ID. The interval geometry does not decide these product policies.

Keep Calendar Time Outside the Core Algorithm

Convert timestamps to a monotonic or UTC timeline before interval arithmetic, retaining zone metadata for display. Local times can be ambiguous or nonexistent at daylight-saving transitions. A meeting from 01:30 to 02:30 local may not represent one hour on the transition day. Date-only events and recurrence rules add separate semantics.

Clock times from different systems also have skew. Event-time intervals should come from a named authority, not receive order. For a coding question, state that inputs are comparable numeric endpoints unless the prompt explicitly tests calendars. In production follow-ups, parse and validate at the boundary, perform algorithms on canonical instants, then format using the requested timezone.

Diagnose Bugs with Minimal Counterexamples

If touching intervals incorrectly conflict, test [1,3) and [3,5). If a nested interval shortens the union, test [1,10) followed by [2,3) and ensure the end uses max. If the maximum count spikes at a shared endpoint, test one end and one start at time 3 and inspect tie order. If output changes across runs, add equal starts with distinct IDs and define the secondary key.

Empty input should return an empty result. One interval should round-trip. Duplicates should follow the merge or payload policy. Reversed endpoints should be rejected or normalized only if the API says so; silently swapping can hide bad data. Very large endpoints test overflow in differences and inclusive-to-half-open conversion.

Use properties: merged output is sorted and pairwise non-overlapping under the chosen rule; its covered measure matches the input union; applying merge twice is idempotent; permuting input does not change canonical geometry. For room counts, compare the heap result with a small event-sweep oracle.

Make the Answer Reviewable

Turn the interval coding design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

Practice Five Related PracHub Questions

The first column links directly to five complete PracHub question records. Treat them as drills for transferable reasoning. They are candidate-reported practice evidence, not a forecast of a specific company interview.

A 45-Minute Interview Structure

Spend four minutes on endpoint, validity, payload, and output rules. Draw the shared-endpoint truth table. Use ten minutes for the baseline scan, eight for a sweep or heap follow-up, and eight for a narrated tie case. Spend seven on complexity and deterministic output, five on timezone or update follow-ups, and three on properties. Keep comparisons symbolic until the contract is fixed.

Final Takeaway

Correct interval code begins with boundaries. Under [start,end), touching intervals do not conflict and sweep ends precede starts at a tie. Merging, conflict detection, room allocation, and maximum concurrency require different active state even when all begin with sorting. Carry validation, payload, and time-zone policies separately so the core geometry stays auditable.

Sources and Further Reading

• Python sorting HOWTO
• Python heapq
• RFC 5545 iCalendar
• CP-Algorithms sweep line pattern

Research note: Technical documentation and linked PracHub practice records were checked on September 13, 2026. Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.