Calendar Without Double Booking
Problem
A meeting room accepts booking requests one at a time. Each request is a half-open span [start, end), so a booking ending at 20 does not clash with one starting at 20. book(start, end) must add the span and return True if it overlaps no accepted booking, and otherwise leave the calendar unchanged and return False. There are up to 1,000 requests and 0 ≤ start < end ≤ 10^9. Keep the accepted bookings sorted so that each request is checked against only its neighbours.
Examples
Input: book(10, 20), book(15, 25), book(20, 30)
Output: [True, False, True]
Why: [15, 25) overlaps [10, 20); [20, 30) only touches itInput: book(5, 10), book(1, 5), book(3, 4)
Output: [True, True, False]
Why: [3, 4) falls inside [1, 5)Input: book(1, 2), book(1, 2)
Output: [True, False]
Why: edge case, the same span twiceHints
0 / 3
Two half-open spans [a, b) and [c, d) overlap exactly when a < d and c < b.
If the accepted bookings are kept sorted by start and never overlap each other, a new span can only clash with the booking just before its position or the booking just after it.
Find the insertion point with bisect_right on the start times. Reject if the previous booking ends after the new start, or if the next booking starts before the new end; otherwise insert at that point.
Solution
Accepted bookings never overlap, so when they are sorted by start their end times are sorted too, and a new span only has to be compared with its two neighbours in that order. bisect_right on the start times finds where the new span would go: the booking just before it is the latest one starting at or before the new start, and it clashes only if it ends after that start; the booking just after it clashes only if it starts before the new end. Using half-open spans makes touching bookings legal with plain strict comparisons. Each check is O(log n); inserting into a Python list shifts elements, so a booking costs O(n) in the worst case, which a balanced tree or sorted container would bring down to O(log n). Space is O(n).
from bisect import bisect_right
class Calendar:
def __init__(self):
self.starts, self.ends = [], []
def book(self, start, end):
i = bisect_right(self.starts, start)
if i and self.ends[i - 1] > start: # previous one still running
return False
if i < len(self.starts) and self.starts[i] < end: # next one starts too soon
return False
self.starts.insert(i, start)
self.ends.insert(i, end)
return True
def run(requests):
calendar = Calendar()
return [calendar.book(s, e) for s, e in requests]
print(run([(10, 20), (15, 25), (20, 30)])) # -> [True, False, True]
print(run([(5, 10), (1, 5), (3, 4)])) # -> [True, True, False]
print(run([(1, 2), (1, 2)])) # -> [True, False]Stuck on the idea rather than the code? Insert Interval covers it.