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: This question evaluates proficiency with interval manipulation and range-query data structures — including line-sweep sort-and-merge techniques, segment or interval trees, coordinate compression, handling duplicates and off-by-one boundary issues — along with time and space complexity analysis.