Algorithm · Amazon · Medium
You are tasked with implementing a system that maintains a collection of intervals, initially empty. The system supports two operations: ADD l r – insert the closed interval [l, r]. It is guaranteed that the new interval does not intersect any previously inserted interval. CHECK x – return true if the integer x lies within at least one stored interval; otherwise return false. Before coding, analyze the per-query time complexity and overall space usage of the following three…