01 / The idea
Ask what is active at the same time.
If a calendar has n intervals, an all-pairs check considers roughly n(n − 1) / 2 pairs. That can be acceptable for a tiny list, but it spends the same
work on windows that are weeks apart.
The sweep line orders the moments where the active set changes. A start adds one window; an end removes one. The active count after each boundary gives peak concurrency, and the active members tell us which new start conflicts with which existing work.
The interval convention is part of the result. This lesson uses half-open windows [start, end): an end at 09:30 and a start at 09:30 do not overlap.
Find the crowded part of the release calendar.
08:00startdeploy-apiEnd events come first at equal times, which makes touching windows safe.
Order the boundary events
Each interval becomes a start and an end event. End first at the same minute, so [start, end) windows that touch are not overlaps.
Reduced motion: choose a scene to see its completed state.
Read this scene
Each interval becomes a start and an end event. End first at the same minute, so [start, end) windows that touch are not overlaps.
Each interval becomes a start and an end event. End first at the same minute, so [start, end) windows that touch are not overlaps. 1 boundary events ordered.
Watch and Step through replay the ordered events and active set. Try it runs the TypeScript model on your edited calendar.
Step through the boundary order, the active set, and the capacity decision. Then edit the calendar to see which conflicts disappear when an end and start touch.
02 / Name the rule
End before start when the clock ties.
[a, b) overlaps [c, d) iff max(a, c) < min(b, d)
Make two events per interval. Sort by time; when times tie, process ends before starts. On a start, every currently active interval overlaps the incoming one, so record those pairs before adding it. On an end, remove the interval. The active set is the sweep's state.
Make two boundaries
A start and end event are enough to describe when an interval changes the active set.
Resolve equal times
End-before-start encodes the half-open contract and prevents touching false positives.
Keep what is active
Count the active set, record conflicts at starts, and retain the peak range.
Why not store every pair?Output can still be large
The sweep avoids testing pairs that cannot overlap, but a highly crowded calendar can
still produce many real conflicts. No algorithm can return c conflict records in
less than O(c) output work. If you need only peak concurrency, omit pair reporting and keep
a count or active IDs appropriate to that decision.
03 / Follow one operation
Six windows reveal a three-way bottleneck.
The release calendar peaks at three active windows from 09:00 to 09:45, exceeding the capacity of two. The replay makes the 09:30 handoff visible: the API deploy ends before the CDN purge begins, so those two do not conflict even though their times share a boundary. The count drops to two and climbs back to three within the same minute, so the peak carries on until the DB backup ends at 09:45.
The sweep reports the first stretch at the highest count, and a handoff like this one doesn’t break it: back-to-back segments at the peak count merge. A dip or a gap ends the stretch. After 09:45 the calendar never holds more than two windows again, so seven conflicts and one 45-minute peak are the whole report.
04 / Read the shape
The event list is the reusable boundary.
Basic form is the sweep itself: emit and order boundaries, then record active windows, conflicts, and the peak. In the wild is the contract around it: errors, types, validation, and formatting. At the call site compares peak concurrency with a capacity policy. The scan is deterministic because equal-time event order is explicit.
Turn each interval into a start and an end event, sort ends before starts at equal times, then sweep: record conflicts at each start, update the active set, and keep the first peak stretch.
export function scanWindows(values: Window[]): SweepResult {
validateWindows(values);
const order = new Map(values.map((window, index) => [window.id, index]));
const byId = new Map(values.map((window) => [window.id, window]));
const events = values.flatMap((window) => [
{ time: window.start, kind: 'start' as const, id: window.id },
{ time: window.end, kind: 'end' as const, id: window.id }
]);
events.sort(
(left, right) =>
left.time - right.time ||
eventOrder(left.kind) - eventOrder(right.kind) ||
order.get(left.id)! - order.get(right.id)!
);
const active = new Map<string, Window>();
const conflictMap = new Map<string, Conflict>();
const steps: SweepStep[] = [];
let peak = 0;
let peakStart = 0;
let peakEnd = 0;
for (let index = 0; index < events.length; index += 1) {
const event = events[index];
const conflictIds: string[] = [];
if (event.kind === 'end') {
active.delete(event.id);
} else {
const incoming = byId.get(event.id)!;
for (const current of active.values()) {
const start = Math.max(current.start, incoming.start);
const end = Math.min(current.end, incoming.end);
if (start < end) {
const key = pairKey(current.id, incoming.id, order);
conflictMap.set(key, {
left: key.split(' ↔ ')[0],
right: key.split(' ↔ ')[1],
start,
end
});
conflictIds.push(current.id);
}
}
active.set(event.id, incoming);
}
// Only a gap before the next event is real time; events at the same minute are one instant.
const nextTime = events[index + 1]?.time ?? event.time;
if (nextTime > event.time) {
if (active.size > peak) {
peak = active.size;
peakStart = event.time;
peakEnd = nextTime;
} else if (active.size === peak && event.time === peakEnd) {
// Still at the peak straight after it: extend the first peak rather than start a new one.
peakEnd = nextTime;
}
}
steps.push({
time: event.time,
kind: event.kind,
id: event.id,
activeIds: orderedIds(active, order),
conflictIds: [...new Set(conflictIds)].sort(
(left, right) => order.get(left)! - order.get(right)!
),
peak
});
}
return {
events,
steps,
conflicts: [...conflictMap.values()].sort(
(left, right) =>
order.get(left.left)! - order.get(right.left)! ||
order.get(left.right)! - order.get(right.right)!
),
peak,
peakStart,
peakEnd
};
}
function eventOrder(kind: SweepEvent['kind']): number {
return kind === 'end' ? 0 : 1;
}
function pairKey(left: string, right: string, order: Map<string, number>): string {
return order.get(left)! < order.get(right)! ? `${left} ↔ ${right}` : `${right} ↔ ${left}`;
}
function orderedIds(active: Map<string, Window>, order: Map<string, number>): string[] {
return [...active.keys()].sort((left, right) => order.get(left)! - order.get(right)!);
}func ScanWindows(values []Window) (SweepResult, error) {
if err := validateWindows(values); err != nil {
return SweepResult{}, err
}
order := map[string]int{}
byID := map[string]Window{}
events := make([]SweepEvent, 0, len(values)*2)
for index, window := range values {
order[window.ID] = index
byID[window.ID] = window
events = append(events, SweepEvent{Time: window.Start, Kind: "start", ID: window.ID})
events = append(events, SweepEvent{Time: window.End, Kind: "end", ID: window.ID})
}
sort.Slice(events, func(left, right int) bool {
if events[left].Time != events[right].Time {
return events[left].Time < events[right].Time
}
if eventOrder(events[left].Kind) != eventOrder(events[right].Kind) {
return eventOrder(events[left].Kind) < eventOrder(events[right].Kind)
}
return order[events[left].ID] < order[events[right].ID]
})
active := map[string]Window{}
conflicts := map[string]Conflict{}
steps := make([]SweepStep, 0, len(events))
peak, peakStart, peakEnd := 0, 0, 0
for index, event := range events {
conflictIDs := []string{}
if event.Kind == "end" {
delete(active, event.ID)
} else {
incoming := byID[event.ID]
for _, current := range active {
start := max(current.Start, incoming.Start)
end := min(current.End, incoming.End)
if start < end {
left, right, key := orderedPair(current.ID, incoming.ID, order)
conflicts[key] = Conflict{Left: left, Right: right, Start: start, End: end}
conflictIDs = append(conflictIDs, current.ID)
}
}
active[event.ID] = incoming
}
// Only a gap before the next event is real time; events at the same minute are one instant.
nextTime := event.Time
if index+1 < len(events) {
nextTime = events[index+1].Time
}
if nextTime > event.Time {
if len(active) > peak {
peak = len(active)
peakStart, peakEnd = event.Time, nextTime
} else if len(active) == peak && event.Time == peakEnd {
// Still at the peak straight after it: extend the first peak rather than start a new one.
peakEnd = nextTime
}
}
steps = append(steps, SweepStep{
Time: event.Time, Kind: event.Kind, ID: event.ID,
ActiveIDs: activeIDs(active, order), ConflictIDs: uniqueOrdered(conflictIDs, order), Peak: peak,
})
}
orderedConflicts := make([]Conflict, 0, len(conflicts))
for _, conflict := range conflicts {
orderedConflicts = append(orderedConflicts, conflict)
}
sort.Slice(orderedConflicts, func(left, right int) bool {
return order[orderedConflicts[left].Left] < order[orderedConflicts[right].Left] ||
(order[orderedConflicts[left].Left] == order[orderedConflicts[right].Left] && order[orderedConflicts[left].Right] < order[orderedConflicts[right].Right])
})
return SweepResult{Events: cloneEvents(events), Steps: steps, Conflicts: orderedConflicts, Peak: peak, PeakStart: peakStart, PeakEnd: peakEnd}, nil
}
func uniqueOrdered(values []string, order map[string]int) []string {
seen := map[string]bool{}
result := []string{}
for _, value := range values {
if !seen[value] {
seen[value] = true
result = append(result, value)
}
}
sort.Slice(result, func(left, right int) bool { return order[result[left]] < order[result[right]] })
return result
}
func eventOrder(kind string) int {
if kind == "end" {
return 0
}
return 1
}
func orderedPair(left, right string, order map[string]int) (string, string, string) {
if order[left] < order[right] {
return left, right, left + " ↔ " + right
}
return right, left, right + " ↔ " + left
}
func activeIDs(active map[string]Window, order map[string]int) []string {
ids := make([]string, 0, len(active))
for id := range active {
ids = append(ids, id)
}
sort.Slice(ids, func(left, right int) bool { return order[ids[left]] < order[ids[right]] })
return ids
}
func cloneEvents(values []SweepEvent) []SweepEvent { return append([]SweepEvent(nil), values...) }Reading the TypeScriptActive state changes at boundaries
The TypeScript model keeps an active map and sorts IDs by input order for stable trace output. It records pair intersections only when a start arrives while the other window is active.
Reading the GoSame half-open event policy
The Go implementation applies the same end-before-start ordering, active-set update, peak rule, and stable conflict ordering. The printed fixture therefore agrees across languages.
What is refusedMake interval semantics explicit
Both versions accept at most 64 intervals in a seven-day integer-minute range. Empty windows, duplicate IDs, reversed endpoints, and invalid capacities are rejected before the sweep returns a decision.
05 / Try a decision
Does the 09:30 handoff overlap?
The API deploy ends and the CDN purge starts at the same minute. The half-open rule and the tie order decide what the sweep records.
Peak concurrency is a trigger, not a schedule. The sweep can tell the release controller that capacity two is exceeded and name the conflicting work. It cannot decide which team has priority, whether a backup can move, or whether two jobs are safe to run together. Those are operational policies on top of the interval facts.
Operational rule: use the scan to surface an explicit conflict set and peak window, then let an owner choose the remediation.
Try three boundary policiesThe tie rule changes the answer
- Half-open: use for scheduled slots where one job may begin as another ends.
- Closed: use when sharing an endpoint is itself a collision, but process starts before ends at equal times.
- Open: use only when both endpoints are excluded; write the rule down because it is easy to misread.
06 / Follow the cost
Sort the boundaries once; pay for real output.
The event sort dominates the basic scan at O(n log n). The active-set pass is linear after sorting. Reporting every real overlap adds O(c), where c can be quadratic in a calendar whose windows all overlap. If the decision only needs the peak, do not materialize the conflicts. The code on this page also copies and sorts the active IDs at every event so the film can replay them; the table lists that trace on its own row.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Create boundary events | O(n) | O(n) | Each interval contributes one start and one end event. |
| Sort the events | O(n log n) | O(n) | Sort by time, with end before start at equal times for half-open windows. |
| Sweep active concurrency | O(n) | O(n) | Add at starts, remove at ends, and keep the first stretch at the largest count. |
| Report pairwise conflicts | O(n + c) | O(n + c) | Every window active at a start overlaps it, so each comparison is a reported pair. c is the number of overlaps; a dense schedule can still produce many. |
| Record the replay trace (this lesson) | O(n · k log k) | O(n · k) | k is the peak count. Each of the 2n events copies and sorts the active IDs for the film. Drop the trace and the rows above are the whole cost. |
| Compare every pair | O(n²) | O(1) or O(c) | The simple baseline checks each pair even when most windows are far apart. |
07 / Give it a real job
A release calendar checked on every pull request.
The operations team keeps next week’s release calendar as a file in the repository. Every
pull request that edits it runs a CI job that calls evaluateCapacity from At the call site with the team’s capacity of two, and fails the check when the
result comes back unsafe. This calendar fails: three windows run from 09:00 to 09:45, and the
job prints the seven conflicting pairs so the author can see which windows collide.
The check owns the facts: the peak count, the first stretch at that count, and every pair that overlaps under the half-open rule. It leaves out the fix. Which job moves, which team has priority, and whether two jobs are actually safe together stay with the people reviewing the change.
This runs in the CI job that reads the calendar file; the page that shows the calendar displays the result, and nothing in a component computes it.
08 / Make the call
Choose the interval algorithm that matches the question.
Use a sweep line for overlap, peak concurrency, or event-driven range queries over a batch. Use weighted interval scheduling when the goal is to choose a highest-value compatible subset, not merely report conflicts.
Use Quickselect when one rank in a batch matters, and max flow when the constraint is capacity through a network rather than simultaneous time windows.
Three boundaries to rememberThe event policy is part of correctness
- Endpoint meaning: half-open and closed intervals produce different conflicts.
- Output size: a fast scan cannot make a quadratic conflict list small.
- Batch versus stream: sorting needs the events; a live scheduler may maintain a different ordered structure.
09 / Take the idea with you
Explain a crowded calendar without saying “sweep line.”
“Write down every moment something starts or stops, and put those moments in time order. When two land on the same minute, let the one that stops go first. Walk the list keeping a tally of what is running: add one at a start, take one away at a stop. Anything already running when something new starts overlaps it, and the highest tally is the busiest the day gets.”
Before moving on, open your own calendar for tomorrow. List each meeting’s start and end times in order, walk the list, and find the most things you are booked for at once.
Connections to follow nextRelated lessons
- Monotonic stacks, interval problems, and string matching merges overlapping windows after one sort by start, the sibling question to “how many at once?”
- Weighted interval scheduling chooses which compatible windows to keep when they can’t all run.
- Ordered map keeps windows in order as they are added and removed, for a live scheduler that can’t sort a finished batch.