Compute total covered interval length

Given a list of integer intervals [l, r) (half-open), compute the total length covered by at least one interval. Intervals may overlap or be nested. Return the length and explain time and space complexity. Implement two approaches: (a) sort-and-merge line sweep; (b) a segment tree or interval tree that supports incremental add/remove intervals and querying the total covered length after each update. Discuss handling large coordinate ranges via coordinate compression, treatment of duplicates, and common off-by-one pitfalls.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute total covered interval length

Given a list of integer intervals [l, r) (half-open), compute the total length covered by at least one interval. Intervals may overlap or be nested. Return the total covered length as an integer.

Because the intervals are half-open [l, r), two intervals that only touch at a single point (e.g. [1, 2) and [2, 4)) form one contiguous covered span of combined length, with no double counting. Zero-length intervals where l == r contribute nothing.

The classic approach is a sort-and-merge line sweep: sort the intervals by start, then walk through them maintaining the current merged span, accumulating its length each time a gap appears. This runs in O(n log n) time. The prompt also invites discussing a segment tree with coordinate compression that supports incremental add/remove and querying covered length after each update; for this console you implement the static line-sweep computation.

Input: a list of [l, r] pairs (each interpreted as the half-open interval [l, r)). Output: the integer total covered length.

Constraints

• 0 <= number of intervals <= 10^5
• Each interval is [l, r) with l <= r (l == r is a valid zero-length interval contributing 0)
• Coordinates may be negative; -10^9 <= l, r <= 10^9
• Intervals may overlap, be nested, or be exact duplicates

Examples

Example 1

Input: ([[1, 3], [2, 5], [7, 9]],)
Output: 6

Explanation: [1,3) and [2,5) merge into [1,5) (length 4); [7,9) adds 2. Total 6.

Example 2

Input: ([],)
Output: 0

Explanation: No intervals, so nothing is covered.

Hints

1. Sort the intervals by their start coordinate, then sweep left to right keeping one 'current' merged span.
2. Since the intervals are half-open [l, r), an interval whose start equals the current end (l == cur_r) still merges into the same contiguous span — use l <= cur_r as the overlap test.
3. Drop zero-length intervals (l == r) up front, and only add the current span's length to the total when the next interval starts a fresh, non-overlapping span.
4. Coordinate compression plus a segment tree gives an alternative that also supports incremental add/remove, but for a one-shot static query the O(n log n) line sweep is simplest.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given a list of integer intervals [l, r) (half-open), compute the total length covered by at least one interval. Intervals may overlap or be nested. Return the length and explain time and space complexity. Implement two approaches: (a) sort-and-merge line sweep; (b) a segment tree or interval tree that supports incremental add/remove intervals and querying the total covered length after each update. Discuss handling large coordinate ranges via coordinate compression, treatment of duplicates, and common off-by-one pitfalls.

Recommended Approach

Sort intervals by start, then keep a current merged interval. For each next interval, merge it when next.start <= current.end for overlapping half-open intervals, and use next.start == current.end as mergeable only when the prompt says contiguous intervals should be merged. Otherwise append the current interval and start a new one.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Time: O(n log n) for sorting. Space: O(n) for the output, or O(1) auxiliary space if sorting in place is allowed.

Edge Cases and Tests

Empty input, one interval, nested intervals, duplicate intervals, negative coordinates, zero-length intervals, and intervals touching exactly at the boundary.