⚡Flashcard Drill➔
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

  1. Keep the accepted bookings in a list sorted by start.
  2. Two half-open intervals overlap when existing.start < new.end and new.start < existing.end.
  3. Scan the bookings and reject if any overlap is found; otherwise insert the new booking in sorted position.
  4. 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: insort maintains the sorted invariant that the scan relies on.
  • Returning true before 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems