This question evaluates competency in designing and implementing efficient dynamic interval data structures, handling correctness for duplicate and nested intervals, extending APIs with cancellation and point queries, and performing rigorous worst-case time/space analysis and resource-adaptation.
Design and implement a booking system like LeetCode 732 (My Calendar III). Provide a class with methods: book(start, end) using half-open intervals [start, end) where 0 ≤ start < end ≤ 1e9. After each call, return the maximum number of concurrent bookings seen so far. Constraints: up to 100,000 operations; target O(log n) amortized per update and O(n) space. (1) Implement using either (a) a sweep-line difference map over a balanced BST (ordered map) or (b) a segment tree with lazy propagation and coordinate compression—explain your choice and prove correctness. (2) Precisely handle duplicate and nested intervals; state your inclusive/exclusive boundary convention and provide unit tests that expose off-by-one bugs (e.g., book(10,20), book(20,30), book(15,25)). (3) Follow-up: add cancel(start, end) that removes a previously booked interval and keeps the returned max-k correct for all future calls; also add query(t) that returns the number of active bookings at time t in O(log n). (4) Analyze worst-case time/space, show how your data structure avoids O(n) per operation in adversarial sequences (e.g., many overlapping single-point intervals), and discuss how you would adapt it if recursion limits or memory fragmentation become an issue.