NeetCode #844LC-729MediumIntervals
← Back to All Problems#844 · #729 · My Calendar I(我的日程安排表 I)
📌 Problem Statement & Constraints
Design a calendar that stores non-overlapping half-open intervals
[start, end). Implement book(start, end) which returns true and adds the booking if it does not cause a double booking, or false otherwise. Constraints: 0 <= start < end <= 10^9, at most 1000 calls to book.💡 Core Algorithmic Approaches
- Keep the accepted bookings in a list sorted by start.
- Two half-open intervals overlap when
existing.start < new.endandnew.start < existing.end. - Scan the bookings and reject if any overlap is found; otherwise insert the new booking in sorted position.
- With at most 1000 calls, an O(n) scan per booking is comfortably within limits; a balanced tree would give O(log n).
💻 Benchmark Python3 Implementation
class Solution:
def __init__(self):
self.bookings = [] # sorted by start
def book(self, start: int, end: int) -> bool:
from bisect import insort
for s, e in self.bookings:
if s < end and start < e: # strict overlap for half-open ranges
return False
insort(self.bookings, (start, end))
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n) per book: a linear scan plus an insertion into a Python list.
💾 Space Complexity
O(n): the stored bookings.
⚠️ Interview Pitfalls & Follow-ups
- Using
<=in the overlap test: half-open intervals[1,2)and[2,3)do not overlap, so both comparisons are strict. - Storing closed intervals: the problem uses half-open ranges, which changes the overlap condition.
- Inserting without keeping order:
insortmaintains the sorted invariant that the scan relies on. - Returning
truebefore inserting: the booking must be recorded on success, otherwise later calls miss it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.