Problem
LeetCode #731 — one-liner.
- Allow double bookings, but reject anything that would create a triple booking.
Key insight
Track the double-booked regions.
- Keep two lists:
bookings(all accepted events) andoverlaps(the regions where two events already coincide). - A new booking is rejected iff it overlaps any
overlapsregion (that would be three-deep). - Otherwise, record the intersections with each existing booking into
overlaps, then append the booking itself.
Solution template
Two scans per call.
# reject if intersects any existing double-booking
for os, oe in overlaps:
if start < oe and end > os: return False
# record new double-bookings
for bs, be in bookings:
if start < be and end > bs:
overlaps.append((max(start, bs), min(end, be)))
bookings.append((start, end)); return TrueComplexity
Per-call cost.
- Time
O(n)per call — two linear scans over the stored lists. - Space
O(n)— bookings + overlaps grow together.
Edge cases
Two to remember.
- Overlapping with an existing double-booking → reject (would be triple).
- An accepted booking that overlaps several existing ones records a separate double-booked region per existing booking.
Comments
Comments are disabled in this environment. Set
PUBLIC_GISCUS_REPO,PUBLIC_GISCUS_REPO_ID, andPUBLIC_GISCUS_CATEGORY_IDto enable.