Google phone

似乎可以用tree
tree node: interval
insertion O(lgn）, search O(lgn)

https://www.geeksforgeeks.org/interval-tree/
觉得这个可行

我觉得O(n) 可以接受 毕竟worst case  interval 已经排序了 你从小加到大 也是O(n)  当然可以写个best log(n) 的
真.log(n) 不是不可能 而是得有一个balanced BST 楼上说的interval tree的前提也是balanced BST 但是电面总不至于写红黑树吧哈哈lol