← 返回 amazon 的题目列表Efficient Interval Manager with Fast Total Coverage Query
类型:online_judge
amazon
Implement an IntervalManager interface with two methods:
addInterval(int from, int to): Adds an interval [from, to].
getTotalCoveredLength() -> int: Returns the total length covered by all added intervals.
Design an algorithm to efficiently handle these method calls, aiming to have the worst-case time complexity of getTotalCoveredLength() better than O(n log n). You can assume that addInterval can be called up to 10^5 times, and each interval [from, to] meets 0 <= from < to <= 10^9.
Example
Input
[(1, 3), (2, 5), (6, 8)]