Implement and extend My Calendar III

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.