self.intervals is a sorted list of real numbers in which I store the following intervals:
[self.intervals, self.intervals), etc.
So I do a binary search to check if I can insert and insert when possible. Meanwhile, I hope the list insertion is optimized through some sort of linked list ideas (on which I have zero knowledge).
If anyone knows how this part of
list is implemented in Python, please let me know! I appreciate it!
Btw, it would be theoretically optimal to use some sort of self-balancing binary search tree, like red-black tree. But since
list object is so optimized, I don't think red-black tree can outrun this code unless the data is really really HUGE.
def __init__(self): self.intervals =  def book(self, start, end): """ :type start: int :type end: int :rtype: bool """ if end <= start: return False i = bisect.bisect_right(self.intervals, start) if i % 2: # start is in some stored interval return False j = bisect.bisect_left(self.intervals, end) if i != j: return False self.intervals[i:i] = [start, end] return True