EF-T06: Earliest peak interval overlap

Exercise contract#

Given integer intervals [start,end), return an object with peak, the largest number of simultaneously active nonempty intervals, and earliest, the earliest coordinate where that positive peak begins. Ignore zero-length intervals. Reject any interval with start>end. With no nonempty intervals return {peak:0, earliest:null}. Do not expand intervals point by point.

Constraints

• 0 <= intervals.length <= 200,000.
• Each interval has exactly two integer endpoints in [-1,000,000,000, 1,000,000,000].
• Intervals are half-open: start is included and end is excluded.
• Duplicate intervals are distinct contributions to active count.
• Zero-length intervals are valid but ignored; reversed intervals are validation errors.

Examples

intervals=[[1,4],[2,5],[4,6],[5,5]]

{peak:2, earliest:2}The peak first reaches two on [2,4). At 4 one interval ends as another begins, so grouped half-open events keep the count at two without creating three.

intervals=[[3,3]]

{peak:0, earliest:null}A half-open zero-length interval contains no coordinate and is ignored.

Derive the approach#

Baseline: For every pair of intervals, test overlap and try to infer the maximum, or enumerate every integer coordinate. Pairwise reasoning is O(n^2) and does not directly identify higher-order overlap; coordinate enumeration depends on coordinate magnitude and is invalid for large gaps.

1. A nonempty [start,end) interval adds one active item beginning at start and removes it at end.
2. Accumulate +1 and -1 into a map keyed by coordinate, which groups simultaneous starts and ends.
3. Visit coordinates in increasing order and apply the entire net delta before interpreting activity beginning at that coordinate.
4. When active becomes strictly larger than peak, record both the new peak and the current coordinate. Do not replace earliest on an equal later peak.
5. If no nonempty interval produced positive activity, preserve earliest=null rather than inventing a coordinate.

Time

O(n log n) for n intervals, dominated by ordering at most 2n distinct event coordinates.

Space

O(n) for grouped event deltas.

Assumptions

Endpoint comparison and active counts fit the chosen integer types; zero-length intervals are ignored before event creation; the input is static rather than an online update stream.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def earliest_peak(intervals):
    delta = {}
    for start, end in intervals:
        if start > end:
            raise ValueError("expected start <= end")
        if start == end:
            continue
        delta[start] = delta.get(start, 0) + 1
        delta[end] = delta.get(end, 0) - 1

    active = 0
    peak = 0
    earliest = None
    for coordinate in sorted(delta):
        active += delta[coordinate]
        if active > peak:
            peak = active
            earliest = coordinate
    return {"peak": peak, "earliest": earliest}

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

final class TransferT06 {
    record Interval(int start, int end) {}
    record Peak(int peak, Integer earliest) {}

    static Peak earliestPeak(List<Interval> intervals) {
        Map<Integer, Integer> delta = new TreeMap<>();
        for (Interval interval : intervals) {
            if (interval.start() > interval.end()) {
                throw new IllegalArgumentException("expected start <= end");
            }
            if (interval.start() == interval.end()) continue;
            delta.merge(interval.start(), 1, Integer::sum);
            delta.merge(interval.end(), -1, Integer::sum);
        }
        int active = 0;
        int peak = 0;
        Integer earliest = null;
        for (Map.Entry<Integer, Integer> event : delta.entrySet()) {
            active += event.getValue();
            if (active > peak) {
                peak = active;
                earliest = event.getKey();
            }
        }
        return new Peak(peak, earliest);
    }
}

Deterministic test plan#

Transfer and follow-ups#

• Also return total union length; explain why length is accumulated before applying the current coordinate's delta.
• Return every segment with peak activity rather than only its earliest coordinate.
• Change to closed intervals and define a new equal-coordinate ordering contract before adapting code.

Transfer grouped event reasoning to a capacity invariant, then contrast that query with peak location.

Authorship and review#

Engineering Foundry authored this bounded prompt, tie contract, examples, tests, and code. It is not attributed to an employer and applies a standard sweep-line event technique without claiming originality of that technique.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09, SRC-DSA-CP-INTERVAL-UNION