LeetCode 731 - My Calendar II

LeetCode Problem 731

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set

Solution

Problem Understanding

The problem asks us to design a calendar system that supports booking time intervals while enforcing one important rule: no point in time may be covered by three events simultaneously.

Each event is represented as a half open interval [startTime, endTime). This means the event includes startTime but excludes endTime. For example, the intervals [10, 20) and [20, 30) do not overlap because time 20 belongs only to the second interval.

The book(startTime, endTime) method should attempt to insert a new event into the calendar. If adding this event would create any time range where three events overlap, the booking must be rejected and the calendar state must remain unchanged. Otherwise, the booking succeeds.

The constraints are important:

• 0 <= start < end <= 10^9
• At most 1000 booking calls

The very large time range tells us we cannot use an array indexed by time. However, the relatively small number of operations, only up to 1000, means an O(n^2) style solution is acceptable.

The key observation is that double bookings are allowed, but triple bookings are not. That means we must carefully track regions where two events already overlap. If a new event intersects any of those regions, it would immediately create a triple booking.

Several edge cases are important:

• Adjacent intervals like [10, 20) and [20, 30) should not overlap.
• A booking may overlap multiple existing events separately without creating a triple booking.
• A booking that overlaps an already double booked region by even a single point must be rejected.
• Failed bookings must not modify internal state.

Approaches

Brute Force Approach

A straightforward approach is to store every booked interval and, for each new booking, compute how many events overlap at every relevant segment.

One way to do this is:

1. Add the new interval temporarily.
2. Collect all start and end points.
3. Sweep through the timeline counting active intervals.
4. Reject the booking if the overlap count ever exceeds 2.

This works because a sweep line accurately computes the number of simultaneous events at every point in time.

However, recomputing overlap counts from scratch after every booking is inefficient. If there are n bookings, each insertion may require examining all existing intervals and all boundary points. Over many operations, this becomes unnecessarily expensive.

Optimal Approach

The key insight is that triple bookings occur only when a new interval overlaps an already double booked region.

We maintain two separate lists:

• bookings, all successfully booked intervals
• overlaps, all intervals that are already double booked

When a new event arrives:

1. First check whether it intersects any interval in overlaps.

• If it does, the booking would create a triple booking, so reject it.

2. Otherwise, compare the new interval with all existing bookings.

• Any intersection becomes a new double booked interval, so store it in overlaps.

3. Finally, add the new interval to bookings.

This works because overlaps precisely represents every time range already covered twice.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) per booking	O(n)	Recomputes overlap counts repeatedly
Optimal	O(n) per booking	O(n)	Tracks double booked intervals directly

Algorithm Walkthrough

1. Initialize two lists:

• bookings, stores every successfully booked interval
• overlaps, stores intervals where two bookings already overlap

2. When a new booking [startTime, endTime) arrives, first check it against every interval in overlaps.
3. Two intervals overlap if:

startTime < existingEnd AND endTime > existingStart

This condition ensures there is a non-empty shared region. 4. If the new booking intersects any interval in overlaps, immediately return False.

• That overlap region is already covered by two events.
• Adding another event would create a triple booking.

5. If no triple booking occurs, compare the new interval with every existing interval in bookings.
6. For every overlap found:

• Compute the intersection:

overlapStart = max(startTime, existingStart)
overlapEnd = min(endTime, existingEnd)

• Add this intersection to overlaps.
• This newly created region is now double booked.

7. After processing all existing bookings, append the new interval to bookings.
8. Return True because the booking succeeded.

Why it works

The invariant is that overlaps always contains every region currently booked exactly twice. Before accepting a new booking, we verify that it does not intersect any such region. Therefore, no accepted booking can ever create a triple overlap. Since every newly formed double booked region is added into overlaps, the invariant remains true after every successful insertion.

Python Solution

class MyCalendarTwo:

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

    def book(self, startTime: int, endTime: int) -> bool:

        # Check for triple booking
        for overlap_start, overlap_end in self.overlaps:
            if startTime < overlap_end and endTime > overlap_start:
                return False

        # Record newly created double bookings
        for booked_start, booked_end in self.bookings:
            if startTime < booked_end and endTime > booked_start:
                self.overlaps.append((
                    max(startTime, booked_start),
                    min(endTime, booked_end)
                ))

        # Add the booking
        self.bookings.append((startTime, endTime))

        return True

The implementation directly follows the algorithm described earlier.

The constructor initializes two lists. The bookings list stores all accepted events, while the overlaps list stores regions already booked twice.

Inside the book method, the first loop checks whether the new interval intersects any double booked region. If such an intersection exists, the method immediately returns False because accepting the booking would create a triple overlap.

The second loop computes all new double booked regions created by the incoming interval. For every overlap with an existing booking, the intersection interval is added to overlaps.

Finally, the booking itself is appended to bookings, and the method returns True.

The use of half open intervals is naturally handled by the overlap condition:

startTime < existingEnd and endTime > existingStart

This correctly treats touching intervals as non-overlapping.

Go Solution

type MyCalendarTwo struct {
	bookings [][2]int
	overlaps [][2]int
}

func Constructor() MyCalendarTwo {
	return MyCalendarTwo{
		bookings: make([][2]int, 0),
		overlaps: make([][2]int, 0),
	}
}

func (this *MyCalendarTwo) Book(startTime int, endTime int) bool {

	// Check for triple booking
	for _, interval := range this.overlaps {
		overlapStart := interval[0]
		overlapEnd := interval[1]

		if startTime < overlapEnd && endTime > overlapStart {
			return false
		}
	}

	// Record new double bookings
	for _, interval := range this.bookings {
		bookedStart := interval[0]
		bookedEnd := interval[1]

		if startTime < bookedEnd && endTime > bookedStart {

			newOverlap := [2]int{
				max(startTime, bookedStart),
				min(endTime, bookedEnd),
			}

			this.overlaps = append(this.overlaps, newOverlap)
		}
	}

	// Add booking
	this.bookings = append(this.bookings, [2]int{startTime, endTime})

	return true
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation mirrors the Python version closely. Since Go does not have tuples, intervals are stored as fixed size arrays [2]int.

The slices bookings and overlaps dynamically grow as bookings are added. Helper functions max and min are implemented explicitly because Go does not provide built in integer versions.

Because the constraints are small, using slices with linear scans is entirely sufficient.

Worked Examples

Example 1

Input:

book(10, 20)
book(50, 60)
book(10, 40)
book(5, 15)
book(5, 10)
book(25, 55)

Step 1: book(10, 20)

No overlaps exist.

bookings	overlaps
[(10,20)]	[]

Result: True

Step 2: book(50, 60)

No overlap with existing booking.

bookings	overlaps
[(10,20), (50,60)]	[]

Result: True

Step 3: book(10, 40)

Compare with existing bookings:

• Overlaps (10,20)

New double booked region:

• (10,20)

bookings	overlaps
[(10,20), (50,60), (10,40)]	[(10,20)]

Result: True

Step 4: book(5, 15)

First check against overlaps:

• (5,15) intersects (10,20)

This would create a triple booking on [10,15).

Booking rejected.

bookings	overlaps
[(10,20), (50,60), (10,40)]	[(10,20)]

Result: False

Step 5: book(5, 10)

Check overlaps:

• (5,10) does not intersect (10,20) because endpoint 10 is excluded.

Compare with bookings:

• Overlaps (10,20)? No
• Overlaps (10,40)? No

Add booking.

bookings	overlaps
[(10,20), (50,60), (10,40), (5,10)]	[(10,20)]

Result: True

Step 6: book(25, 55)

Check overlaps:

• Does not intersect (10,20)

Compare with bookings:

• Overlaps (50,60) → add (50,55)
• Overlaps (10,40) → add (25,40)

bookings	overlaps
[(10,20), (50,60), (10,40), (5,10), (25,55)]	[(10,20), (50,55), (25,40)]

Result: True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per booking	Each booking scans existing overlaps and bookings
Space	O(n)	Stores all bookings and overlap intervals

The number of intervals grows linearly with the number of successful bookings. Since there are at most 1000 operations, linear scans are efficient enough.

In the worst case, each booking checks every previously stored booking and overlap interval, resulting in O(n) work per operation.

Test Cases

# Provided example
calendar = MyCalendarTwo()
assert calendar.book(10, 20) == True   # first booking
assert calendar.book(50, 60) == True   # disjoint booking
assert calendar.book(10, 40) == True   # creates double booking
assert calendar.book(5, 15) == False   # would create triple booking
assert calendar.book(5, 10) == True    # boundary touch only
assert calendar.book(25, 55) == True   # multiple overlaps but no triple

# Adjacent intervals
calendar = MyCalendarTwo()
assert calendar.book(10, 20) == True   # first interval
assert calendar.book(20, 30) == True   # adjacent, no overlap
assert calendar.book(30, 40) == True   # adjacent again

# Exact same interval twice
calendar = MyCalendarTwo()
assert calendar.book(10, 20) == True
assert calendar.book(10, 20) == True   # double booking allowed
assert calendar.book(10, 20) == False  # triple booking rejected

# Nested intervals
calendar = MyCalendarTwo()
assert calendar.book(10, 100) == True
assert calendar.book(20, 30) == True
assert calendar.book(40, 50) == True
assert calendar.book(25, 45) == False  # intersects already double-booked region

# Single point boundary checks
calendar = MyCalendarTwo()
assert calendar.book(5, 10) == True
assert calendar.book(10, 15) == True   # no overlap at endpoint
assert calendar.book(15, 20) == True

# Large values
calendar = MyCalendarTwo()
assert calendar.book(0, 10**9) == True
assert calendar.book(1, 2) == True
assert calendar.book(2, 3) == True
assert calendar.book(1, 3) == False    # triple overlap in [1,2)

Test	Why
Provided example	Validates core functionality
Adjacent intervals	Ensures half open interval handling
Exact same interval twice	Confirms double booking is allowed
Third identical interval	Confirms triple booking rejection
Nested intervals	Tests overlap region tracking
Boundary touching intervals	Ensures endpoints are excluded correctly
Large values	Verifies correctness with maximum coordinate range

Edge Cases

One important edge case is adjacent intervals such as [10, 20) and [20, 30). A naive implementation might mistakenly treat these as overlapping because the endpoints touch. The correct overlap condition uses strict inequalities:

start < existingEnd AND end > existingStart

This ensures touching boundaries are not considered overlaps.

Another critical case occurs when multiple overlaps exist independently. For example, a booking may overlap one event in one region and another event in a different region without ever creating a triple booking. The implementation handles this correctly because it tracks only actual double booked intervals, not merely the number of overlapping events globally.

A third subtle case is failed insertions. If a booking would create a triple overlap, the calendar state must remain unchanged. The implementation guarantees this because it checks all existing double booked intervals before modifying either bookings or overlaps. Therefore, rejected bookings never partially update internal state.