230: Intervals, Sorting by Endpoints, Sweep Line, and Event Processing

Learning outcomes

By the end of this lesson, you can:

• explain and apply interval conventions in a realistic implementation;
• explain and apply merge intervals in a realistic implementation;
• explain and apply meeting rooms in a realistic implementation;
• explain and apply sweep-line events in a realistic implementation;
• explain and apply coordinate compression in a realistic implementation.

These outcomes are deliberately practical. You should be able to look at a requirement involving ranges, decide what the endpoints mean, choose an appropriate representation, and defend the choice with an invariant and a complexity analysis. You should also be able to diagnose a result that is wrong only at a boundary, which is where many otherwise reasonable interval implementations fail.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from your previous projects where the same concern appeared. A booking window, a deployment interval, a time-based metric, or a range of array indices will work. The point is to connect the algorithmic model to a real contract: what does the start mean, what does the end mean, and can two ranges that touch be active at the same time?

The goal is not to memorize terminology. It is to make a defensible decision inside an interview-sized problem and a production data-processing problem, so you must reason from constraints rather than memorize a template. In particular, keep the input domain, ordering guarantees, empty-input behavior, and scale visible before choosing a data structure.

Terminology

• Interval conventions: Define closed [a,b], open, or half-open [a,b) semantics. The convention determines whether an endpoint belongs to the interval and therefore whether touching ranges overlap.
• Merge intervals: Sort by start, then extend the current interval while the next overlaps/touches according to the chosen convention.
• Meeting rooms: Sort starts/ends separately or sweep events to track concurrent intervals; the maximum active count gives required resources.
• Sweep-line events: Represent interval start/end (and possibly weighted delta) as events, sort, then update active state.
• Coordinate compression: When coordinates are huge but only a limited set of endpoints matters, map sorted unique coordinates to dense indices for Fenwick/segment structures.
• Geometry extension: More advanced sweeps maintain an ordered active structure as one coordinate moves.

The useful distinction is between an interval's representation and the algorithm operating on it. [2, 5) and [2, 5] may look almost identical in a data file, but they encode different membership and overlap rules. Write that rule down before writing <= or <; the operator is an implementation consequence of the contract, not the contract itself.

Mental model

Treat Intervals, Sorting by Endpoints, Sweep Line, and Event Processing as a design problem with observable inputs, outputs, invariants, and failure modes. Interval problems are often solved by converting ranges into ordered boundary events, then maintaining active state rather than comparing every pair of intervals. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

For a simple half-open interval [start, end), the interval becomes active at start and stops being active at end. At the exact instant end, it is no longer active. That small statement explains why an end event must be processed before a start event at the same coordinate when adjacent reservations are allowed to reuse a room. With closed intervals, the same coordinate can belong to both ranges, so the tie rule changes.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. For merge intervals, the current output is sorted and contains no pair of intervals that should still be merged. For a sweep line, the active state matches the events processed so far. Then choose the mechanism that enforces that invariant.

Deep dive

1. Interval conventions

Define closed [a,b], open, or half-open [a,b) semantics. Endpoint equality changes overlap and event ordering, so the representation is part of correctness.

For two half-open intervals [a, b) and [c, d), they overlap when a < d && c < b. If one ends exactly when the other starts, such as [1, 3) and [3, 5), they do not overlap. For closed intervals, [1, 3] and [3, 5] do overlap because 3 belongs to both. The merge condition must reflect that distinction.

Also decide what an interval with start === end means. Under half-open semantics it contains no points and may represent a zero-duration event. Under a closed convention it contains one endpoint. Negative-length input (start > end) is usually invalid unless the domain explicitly defines a reverse range; reject it at the boundary rather than letting an algorithm assign it accidental meaning.

Decision rule: Use interval conventions deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Half-open intervals are often convenient for durations and array slices because the length is end - start and adjacent intervals compose without overlap, but that convenience does not override an existing business contract.

2. Merge intervals

Sort by start, then extend the current interval while the next overlaps/touches according to the chosen convention. Complexity is dominated by sorting: for n intervals, the usual in-memory implementation is O(n log n) time and O(n) space for the sorted/output representation. If the input can be modified, the auxiliary space may be lower, but the cost of the result still matters.

After sorting, compare only the next interval with the current merged interval. If the next start is within the current end under the chosen convention, extend the end to the larger endpoint. Otherwise, the current interval is complete and a new output interval begins. The invariant is that the output is ordered and already merged through the interval currently being examined.

For closed intervals, touching ranges usually merge when next.start <= current.end. For half-open ranges, whether touching ranges merge is a product decision: mathematical half-open overlap uses <, while a calendar application might intentionally coalesce adjacent bookings even though they do not overlap. Do not silently change that policy inside the sort or merge loop.

Decision rule: Use merge intervals deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. It is a good fit when the output needs a compact union of ranges; it is not the right abstraction when you need to count every concurrent interval or preserve the identity of each event.

3. Meeting rooms

Sort starts/ends separately or sweep events to track concurrent intervals; the maximum active count gives required resources. With separate sorted start and end arrays, advance the next start while it occurs before the next available end, incrementing the active count. Otherwise, consume an end and release a room. This produces O(n log n) time and O(n) space, and it makes the boundary policy visible in the comparison.

An equivalent event sweep stores (+1, start) and (-1, end), sorts by coordinate, and applies a tie rule. For half-open meetings, process an end before a start at the same coordinate if the room can be reused immediately. For closed meetings, process the start first because both meetings are active at that coordinate. The maximum active count is the answer; the invariant is that the count represents resources occupied after all events processed at the current position according to the contract.

Empty input should require zero rooms. A single valid interval requires one room, and invalid intervals should be rejected or reported according to the input contract. The separate-arrays method is often easier to audit; an event list is more extensible when events carry weights or additional metadata.

Decision rule: Use meeting rooms deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Choose based on what must be observed: the maximum count, an assignment of intervals to rooms, or a richer timeline may require different state even though all three start from sorted endpoints.

4. Sweep-line events

Represent interval start/end (and possibly weighted delta) as events, sort, then update active state. Tie ordering must match boundary semantics. A weighted interval contributes a delta such as +weight at its start and -weight at its end; the running total then describes the active weight after each event.

There are two common interpretations of a sweep result: the state before processing a coordinate and the state after processing it. Choose one and keep it consistent. For a maximum-overlap calculation, update the active count at each event and compare the new state with the best result. For measuring the total covered length, first use the current active state over the distance from the previous coordinate to the current coordinate, then apply the events at the current coordinate. Reversing those steps is a classic source of off-by-one and zero-length errors.

When several events share a coordinate, sort by an explicit event priority rather than relying on object or sort stability. Do not use a comparator that returns an ambiguous result for ties. Test a case where one interval ends exactly as another starts; that test proves the tie rule instead of merely exercising the normal path.

Decision rule: Use sweep-line events deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. A sweep is powerful because it replaces pairwise comparisons with one ordered pass, but it requires careful event semantics and enough state to answer the actual question.

5. Coordinate compression

When coordinates are huge but only a limited set of endpoints matters, map sorted unique coordinates to dense indices for Fenwick/segment structures. A coordinate such as 10^12 is not inherently expensive to store, but allocating an array indexed by that value is. Compression keeps the ordering and removes unused gaps.

Collect the coordinates that can affect the answer, sort them, remove duplicates, and map each original coordinate to its index. Preserve the mapping in both directions when the output must report an original coordinate. Be precise about whether an update applies to a point or to the span between two compressed coordinates: the interval [x_i, x_{i+1}) represents a length of x_{i+1} - x_i, not necessarily one unit.

Compression is generally O(k log k) for k coordinates and O(k) additional storage, followed by the cost of the chosen Fenwick tree or segment tree operations. It is safe only when no relevant behavior occurs between the coordinates that were retained. If queries can introduce new coordinates later, compress those coordinates up front or use a structure designed for dynamic coordinates.

Decision rule: Use coordinate compression deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. It is a representation technique, not an algorithm by itself; it does not remove the need to define boundaries, updates, queries, or complexity.

6. Geometry extension

More advanced sweeps maintain an ordered active structure as one coordinate moves. The same event-ordering discipline underlies line-segment and rectangle-area algorithms.

For example, a rectangle-area sweep can process vertical edges by x, maintain active coverage on the y axis, and add coveredY * (currentX - previousX) before applying the next edge updates. The active structure must support range updates and a query for total covered length, which is why a segment tree is often used after coordinate compression. This is more than a larger interval list: the active ordering and overlapping coverage change as the sweep progresses.

Decision rule: Use geometry extension deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. The extension is appropriate when pairwise geometry is too expensive, but it brings stronger requirements around event grouping, active ordering, numeric precision, and memory usage.

Worked example

Consider an interview-sized problem and a production data-processing problem, so you must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which of the concepts above owns each failure mode. For example: “Given valid half-open availability ranges, return their union in ascending order.” That statement answers neither validation nor whether adjacent ranges should be coalesced; those decisions belong in the contract before implementation.

The important move is separation: parsing or validation belongs at the boundary; domain rules belong in the domain/service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns makes a happy-path demo look shorter but makes edge cases much harder to reason about. If input arrives as JSON, validate that each range has numeric endpoints and start <= end before the merge invariant is allowed to depend on it. If the output is persisted, separately define ordering, idempotency, and retry behavior.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

This small function is intentionally not an interval solution. It demonstrates the discipline that should precede one: state what answer means, inspect the input contract, and choose the state needed by the requirement. For an interval merge, the state would normally be the current merged range and an output collection; for meeting rooms, it would be active resources; for a weighted sweep, it would be the running weight and the best observed value. Reusing this function-shaped template without changing the invariant would solve the wrong problem.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For interval data, make those cases concrete: overlapping ranges, no ranges, repeated input, two ranges sharing an endpoint, and a failure while loading the ranges. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. An interval job may receive timestamps from different time zones, duplicated records after a retry, or coordinates larger than the examples suggest. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. Do not let a client-calculated overlap count become an authorization decision, and do not treat a successful sort as proof that the input was valid.

For large event streams, also decide whether all events fit in memory, whether equal-coordinate events must be grouped, and whether numeric totals can overflow the chosen type. A mathematically correct O(n log n) algorithm can still be operationally unsafe if n is unbounded or if it retains every raw record unnecessarily.

Guided lab

Implement merge intervals, minimum meeting rooms, and maximum overlapping weighted intervals with a sweep line. Use half-open semantics and demonstrate how changing tie order breaks one case.

The lab should make the boundary rule observable. Include adjacent intervals such as [1, 3) and [3, 4), overlapping intervals, duplicate intervals, an empty collection, and at least one invalid range. For meeting rooms, show that an end at 3 can release a room before a start at 3; then reverse the event priority and record the incorrect count. For weighted intervals, state whether the reported maximum is the weight after starts and ends at a coordinate or over the open span leading to the next coordinate.

Complete the lab with this discipline:

1. Write the requirement and two non-requirements.
2. List input, output, and error contracts before implementation.
3. Implement the smallest correct vertical slice.
4. Add at least one invalid-input test and one edge-case test.
5. Instrument or inspect the behavior instead of guessing.
6. Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
7. Explain one alternative design and why you did not choose it.
8. Record a short “what would break at 10× scale?” note.

For the complexity note, record the number of intervals and events, the sorting cost, the auxiliary storage, and whether the chosen approach can stream input. A complete result is not just code that returns a number; it is code whose boundary convention, invariant, tests, and resource cost another developer can verify.

Edge cases and failure modes

• Interval conventions: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include equal endpoints and verify whether touching ranges overlap under the documented convention.
• Merge intervals: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include already sorted data, reverse-sorted data, nested ranges, and a chain where each range overlaps the merged result rather than only the previous raw range.
• Meeting rooms: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include all meetings sharing an endpoint and verify the tie order against the room-reuse policy.
• Sweep-line events: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include multiple events at one coordinate, positive and negative weights, and a final end event so active state returns to the expected baseline.
• Coordinate compression: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify duplicate coordinates collapse, original coordinates can be recovered, and gaps use their real lengths rather than compressed index distance.

Common mistakes and debugging

• Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
• Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
• Testing only the happy path and therefore discovering contracts only after integration.
• Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
• Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.
• Using < in one part of the implementation and <= in another without tying either comparison to the interval convention.
• Applying a start event before an end event at a shared endpoint when the contract allows immediate reuse, or doing the reverse for closed intervals.
• Merging against only the previous raw interval instead of the current extended interval, which misses transitive overlap.
• Compressing endpoints but forgetting that the distance between adjacent original coordinates can be greater than one.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Log or inspect the sorted events, including their tie priority; inspect the active count before and after each coordinate; and compare the compressed index mapping with the original coordinates. If the output fails only on equal endpoints, the implementation is usually exposing an undocumented convention rather than a random arithmetic error.

Interview questions

1. What problem does Interval conventions solve, and what trade-off or failure mode would make you choose a different approach?
2. What problem does Merge intervals solve, and what trade-off or failure mode would make you choose a different approach?
3. What problem does Meeting rooms solve, and what trade-off or failure mode would make you choose a different approach?
4. What problem does Sweep-line events solve, and what trade-off or failure mode would make you choose a different approach?
5. What problem does Coordinate compression solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do not stop at naming a sort. State the endpoint convention, the invariant, the dominant complexity, and the test that would expose a wrong tie rule. Also distinguish a method that returns a maximum count from one that must assign each interval to a specific resource; similar input does not imply identical state or output.

Checkpoint

Without notes, explain Intervals, Sorting by Endpoints, Sweep Line, and Event Processing to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

Your explanation should make the endpoint policy explicit. A strong checkpoint answer can explain why sorting reduces the search space, why a sweep needs deterministic tie handling, when compression is safe, and why the usual sorting bound is O(n log n). It should also identify where malformed input is rejected and how a failing boundary case would be inspected.

Mastery checklist

• I can define the core terms precisely.
• I can choose a design from requirements instead of from habit.
• I can implement and test the normal path and edge cases.
• I can explain the runtime, storage, or complexity cost.
• I can identify which layer owns validation, errors, and recovery.
• I can compare at least two reasonable alternatives.
• I can explain how the design changes at larger scale or stricter reliability.

References

• VisuAlgo
• MIT OpenCourseWare: Introduction to Algorithms