Find every clash in a room with two binary searches

transcript

Is the room free at 10:30? Don't scan its whole history. Two binary searches find every clash. Here's why that works.

The naive check tests the request against every booking. Order n, for every single request. Instead, keep each room's bookings sorted. Then the clashes form one run. Order log n.

The trick is a rule the scheduler already enforces. Bookings in one room never overlap. So sorted by start, they're sorted by end too.

Everest on Monday: 10 to 11, then 11 to 12. Someone asks for 10:30 to 11:30. Search the starts. Where would 11:30 go? Index 2. Search the ends, just after 10:30. Index 0. Slice 0 to 2. Both meetings clash. Two searches, done.

But here's the catch. A person's calendar can overlap. Then the ends fall out of order. You need an interval tree.

The speed isn't a clever extra structure. It's the no-overlap rule, keeping the ends in order.

Full breakdown in the lecture.