Compute total covered interval length
Company: LinkedIn
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: Compute total covered interval length evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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
Input: ([[1, 3], [2, 5], [7, 9]],)
Expected Output: 6
Explanation: [1,3) and [2,5) merge into [1,5) (length 4); [7,9) adds 2. Total 6.
Input: ([],)
Expected Output: 0
Explanation: No intervals, so nothing is covered.
Hints
- Sort the intervals by their start coordinate, then sweep left to right keeping one 'current' merged span.
- 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.
- 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.
- 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.