⚡Flashcard Drill➔
NeetCode #845LC-731MediumIntervals
← Back to All Problems

#845 · #731 · My Calendar II(我的日程安排表 II)

📌 Problem Statement & Constraints

Design a calendar that allows double bookings but never triple bookings. Implement book(start, end) which returns true and adds the event if no time is covered by three events, or false otherwise. Constraints: 0 <= start < end <= 10^9, at most 1000 calls to book.

💡 Core Algorithmic Approaches

  1. Keep two lists: all accepted events, and the intervals that are already double-booked.
  2. A new event is rejected if it overlaps any interval in the double-booked list, since that would create a triple booking.
  3. Otherwise, compute its overlap with every existing event and record those overlaps in the double-booked list.
  4. This works because an overlap of the new event with an existing one is exactly a doubly-booked region; keeping them explicit makes the triple check O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def __init__(self):
        self.events = []                        # all single bookings
        self.overlaps = []                      # regions booked exactly twice

    def book(self, start: int, end: int) -> bool:
        for s, e in self.overlaps:
            if s < end and start < e:
                return False                    # would create a triple booking
        for s, e in self.events:
            if s < end and start < e:
                self.overlaps.append([max(s, start), min(e, end)])
        self.events.append([start, end])
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) per book: scanning the events and the overlaps.
💾 Space Complexity
O(n^2) in the worst case for the overlap list, O(n) typically.

⚠️ Interview Pitfalls & Follow-ups

  • Checking the triple condition against the events list: a triple booking arises when the new event overlaps a doubly-booked region, so the check must use the overlaps list.
  • Recording overlaps before the triple check: the rejection test must run first, otherwise a rejected event would pollute the overlaps list.
  • Using closed-interval comparisons: the ranges are half-open, so both comparisons are strict.
  • Forgetting to record the event after a successful booking: the event list drives future overlap computation.
⚡
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