Compute total covered interval length
Overview
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.
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.