My Calendar II: Preventing Triple Bookings

LeetCode 731, My Calendar II, asks you to build a booking system that allows double bookings but draws the line at triple bookings. It is a natural follow-up to My Calendar I, where any overlap was forbidden. Here, the twist is that two events can share time, but three cannot.

This problem teaches you a clean pattern for tracking layered overlaps, one that shows up in scheduling systems, resource allocation, and other interval-based designs.

The problem

You need to implement a MyCalendarTwo class with a single method:

• book(start, end): Attempts to add an event covering the half-open interval [start, end). If adding this event would cause three events to overlap at any point in time, the booking is rejected and the method returns False. Otherwise, the event is added and the method returns True.

A double booking happens when two events share some time. A triple booking happens when three events share some time. Double bookings are fine. Triple bookings are not.

The challenge is figuring out, for each new booking, whether it would push any time slot from a double overlap into a triple overlap.

The key insight

The trick is to maintain two separate lists:

1. bookings: every event that has been successfully booked
2. overlaps: every interval where exactly two existing events already overlap

When a new event comes in, you first check it against the overlaps list. If the new event overlaps with anything in overlaps, that means three events would share time at that intersection, so you reject it.

If the new event passes that check, you then scan through bookings to find any new double overlaps it creates, and add those intersection intervals to overlaps. Finally, you add the new event to bookings.

The intersection of two intervals [s1, e1) and [s2, e2) is [max(s1, s2), min(e1, e2)). This intersection is valid (non-empty) only when max(s1, s2) < min(e1, e2).

The solution

class MyCalendarTwo:
    def __init__(self):
        self.bookings = []
        self.overlaps = []

    def book(self, start, end):
        for os, oe in self.overlaps:
            if start < oe and end > os:
                return False

        for bs, be in self.bookings:
            ss = max(start, bs)
            se = min(end, be)
            if ss < se:
                self.overlaps.append((ss, se))

        self.bookings.append((start, end))
        return True

The first loop is the guard: it checks whether the new event would cause a triple booking. The second loop computes where the new event creates double bookings with existing events. Both loops use the same overlap test, just applied to different lists.

Step-by-step walkthrough

Let's trace through a sequence of calls to see how the two lists evolve.

The critical moment is step 4. When book(5, 15) arrives, it overlaps with [10, 20] in the overlaps list (since 5 < 20 and 15 > 10). That means booking it would create a triple overlap in the [10, 15] range, so it gets rejected.

Complexity analysis

For n calls to book:

Each call to book scans both the overlaps and bookings lists, each of which can grow up to O(n) in size. So each call is O(n), and n calls give O(n^2) total.

The space is O(n) because both lists together hold at most O(n) intervals. Each successful booking adds one entry to bookings and at most O(n) entries to overlaps, but in practice the total across all calls stays manageable.

There are faster approaches using balanced BSTs or segment trees that bring per-call time down to O(n log n) or O(log n), but the two-list approach is clean, easy to implement, and perfectly fine for the constraints LeetCode gives you.

The building blocks

My Calendar II is built from two fundamental patterns that appear across many interval and design problems.

Layered overlap tracking

Instead of trying to count overlaps at every point in time, you track them categorically: single bookings in one list, double overlaps in another. This layered approach avoids the complexity of a full sweep-line or segment tree while still giving you O(1) decision-making per overlap check.

This same "track the dangerous state separately" idea shows up in:

• Meeting Rooms II (track active meetings with a heap to find peak concurrency)
• Non-overlapping Intervals (track the latest end to detect conflicts)
• Insert Interval (separate intervals into before, overlapping, and after)

Intersection computation

Computing the intersection of two intervals with [max(s1, s2), min(e1, e2)) is a micro-pattern that appears constantly in interval problems. Once you can write this from memory and check max_start < min_end for validity, you have a building block that plugs directly into merge intervals, calendar problems, and rectangle overlap checks.

Edge cases

No overlap at all. If the new event does not overlap with any existing booking, it simply gets added to bookings with no new entries in overlaps. The method returns True.

Exact same interval twice. Booking [10, 20) twice is fine (double booking allowed). The overlap [10, 20) gets added to overlaps. A third [10, 20) would be rejected.

Adjacent intervals. [10, 20) and [20, 30) do not overlap because the intervals are half-open. max(10, 20) = 20 and min(20, 30) = 20, so 20 < 20 is false. No intersection.

Single-point overlap. With half-open intervals, an event [10, 11) covering just one unit of time still overlaps with [10, 20). The intersection is [10, 11).

From understanding to recall

You now understand why two lists are enough to prevent triple bookings. The overlaps list captures every region where two events already coexist, and checking a new event against that list tells you immediately whether a triple booking would result. The logic is compact: two loops, one guard check, one intersection computation.

But the details matter. Why do you check overlaps before updating it? Why is the intersection [max(s1, s2), min(e1, e2)) and not something else? Why does the half-open interval convention make adjacent events safe? Each of these is a potential bug if you have not drilled the pattern enough to reproduce it confidently.

The two-list pattern is small enough to practice in isolation. Once it becomes automatic, extending it to three or more layers (as in My Calendar III) is a natural next step.

Related posts

• My Calendar I - The simpler version where any overlap is rejected
• Merge Intervals - The foundational interval merging pattern
• Meeting Rooms II - Another overlap-counting problem using a different approach