Daily bit(e) of C++ | Event booking
Daily bit(e) of C++ #254, Common interview problem: Event booking.
Today, we will look at a common C++ interview problem: Event booking.
Implement a class with a single method: bool book_event(Event);
The method should book an event if there are no other conflicting events and then return true; otherwise, the method should return false.
Events are half-open intervals, i.e. [start, end), i.e. {10,20} and {20,30} are not conflicting.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/K8TGa36WT.
Solution
One way to approach this problem is by keeping the intervals sorted in lexicographical order.
When inserting a new interval, it can only overlap with the interval just before and after. And more than that, since we are ordering by start times first, we only have to check whether the end times overlap.
We can enable lexicographical ordering for the Event type and store events in a std::set, looking up the insertion position using lower_bound.
We can re-use the looked-up position during insertion to avoid the additional log(n) complexity.
