LeetCode 729 - My Calendar I

LeetCode Problem 729

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

Solution

Problem Understanding

The problem asks us to design a calendar system that supports booking events without allowing overlapping intervals.

Each event is represented as a half-open interval [startTime, endTime). This means the event includes startTime, but does not include endTime. For example, the interval [10, 20) contains all times from 10 up to, but not including, 20.

This distinction is very important because two events such as [10, 20) and [20, 30) do not overlap. The first event ends exactly where the second begins, so they are both allowed.

We must implement a class called MyCalendar with two operations:

• The constructor initializes the calendar.
• The book(startTime, endTime) method attempts to insert a new event.

The book method should:

• Return true if the new event does not overlap with any previously booked event.
• Return false if the new event would create a double booking.
• Leave the calendar unchanged when the booking fails.

The constraints tell us several important things:

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

The large possible time values mean we cannot create a timeline array indexed by time. A direct simulation over the time range would be impossible.

However, the number of operations is relatively small, only up to 1000. This means even an O(n) scan for each booking is acceptable because the total work would be around 1,000,000 comparisons in the worst case.

The most important edge cases are:

• Events that touch at boundaries, such as [10, 20) and [20, 30), which are valid.
• Events fully contained inside another event.
• Events that completely contain another event.
• Very large time values near 10^9.
• Booking into an empty calendar.

Understanding interval overlap correctly is the key to solving the problem.

Approaches

Brute Force Approach

The simplest solution is to store every successful booking in a list. Whenever a new booking request arrives, we compare it against every existing event.

Two intervals overlap if:

start < existingEnd AND end > existingStart

This condition means the intervals share at least one moment in time.

If any overlap is found, we immediately return false. Otherwise, after checking all existing bookings, we add the new interval and return true.

This approach is correct because every previously accepted booking is checked individually. If none overlap with the new event, then the booking is safe.

Although this solution is technically brute force, it is fast enough for the problem constraints because there are only up to 1000 bookings.

Better Ordered Approach

A more optimized approach keeps events sorted by start time. Once intervals are sorted, we do not need to compare against every event.

The key observation is that in a sorted list, only neighboring intervals can overlap with a newly inserted interval.

Suppose we insert [start, end) into a sorted structure:

• The previous interval must end before start
• The next interval must begin after end

If both conditions hold, then no overlap exists anywhere else.

This reduces unnecessary comparisons and makes the solution more scalable. In languages with balanced trees or ordered sets, insertion and lookup can be performed efficiently.

For LeetCode 729, both approaches pass comfortably, but the ordered approach demonstrates stronger design principles.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per booking	O(n)	Compare against every existing interval
Optimal	O(log n) search + O(n) insertion	O(n)	Maintain intervals in sorted order

Algorithm Walkthrough

We will use a sorted list of intervals ordered by start time.

Step 1: Store intervals in sorted order

We maintain a list where every interval is sorted by its start time.

This ordering allows us to efficiently locate where a new interval should be inserted.

Step 2: Find insertion position

When booking [startTime, endTime), we use binary search to determine where the interval belongs in the sorted list.

The insertion index tells us:

• All intervals before this index start earlier.
• All intervals after this index start later.

Step 3: Check the previous interval

If there is an interval immediately before the insertion position, we check whether it overlaps.

The overlap condition is:

previousEnd > startTime

If true, the booking fails.

Step 4: Check the next interval

If there is an interval immediately after the insertion position, we check:

endTime > nextStart

If true, the booking overlaps and fails.

Step 5: Insert the interval

If neither neighboring interval overlaps, we insert the interval into the sorted list and return true.

Why it works

Because intervals are stored in sorted order, any overlap can only occur with adjacent intervals around the insertion position.

If the previous interval ends before the new interval begins, and the next interval begins after the new interval ends, then every other interval is automatically non-overlapping due to the sorted ordering.

This invariant guarantees correctness.

Python Solution

from bisect import bisect_left
from typing import List, Tuple

class MyCalendar:

    def __init__(self):
        self.events: List[Tuple[int, int]] = []

    def book(self, startTime: int, endTime: int) -> bool:
        index = bisect_left(self.events, (startTime, endTime))

        # Check previous interval
        if index > 0 and self.events[index - 1][1] > startTime:
            return False

        # Check next interval
        if index < len(self.events) and self.events[index][0] < endTime:
            return False

        self.events.insert(index, (startTime, endTime))
        return True

The implementation maintains a sorted list called events.

The bisect_left function performs binary search to find the correct insertion index for the new interval. Since tuples are compared lexicographically in Python, intervals are naturally ordered by their start times.

After finding the insertion position, the algorithm checks only the neighboring intervals:

• The previous interval may overlap from the left.
• The next interval may overlap from the right.

If neither overlap exists, the interval is inserted into the correct position while preserving sorted order.

The solution directly follows the algorithm walkthrough and efficiently avoids scanning the entire list.

Go Solution

package main

import "sort"

type MyCalendar struct {
	events [][2]int
}

func Constructor() MyCalendar {
	return MyCalendar{
		events: make([][2]int, 0),
	}
}

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

	index := sort.Search(len(this.events), func(i int) bool {
		return this.events[i][0] >= startTime
	})

	// Check previous interval
	if index > 0 && this.events[index-1][1] > startTime {
		return false
	}

	// Check next interval
	if index < len(this.events) && this.events[index][0] < endTime {
		return false
	}

	this.events = append(this.events, [2]int{})

	copy(this.events[index+1:], this.events[index:])

	this.events[index] = [2]int{startTime, endTime}

	return true
}

The Go solution follows the same logic as the Python implementation but uses Go-specific constructs.

sort.Search performs binary search to find the insertion index.

Since Go slices do not support direct insertion, we first expand the slice with append, shift elements using copy, and then place the new interval at the insertion position.

Go integers safely handle the constraint range since 10^9 fits comfortably within the standard int type on LeetCode platforms.

Worked Examples

Example 1

book(10, 20)
book(15, 25)
book(20, 30)

Initial state:

events = []

Operation 1: book(10, 20)

Binary search insertion index:

index = 0

No previous or next interval exists.

Insert interval.

Step	Events
After insertion	[(10, 20)]

Return:

true

Operation 2: book(15, 25)

Current events:

[(10, 20)]

Binary search finds:

index = 1

Check previous interval:

previousEnd = 20
20 > 15

Overlap exists.

Booking fails.

Step	Events
Booking rejected	[(10, 20)]

Return:

false

Operation 3: book(20, 30)

Current events:

[(10, 20)]

Binary search:

index = 1

Check previous interval:

20 > 20 -> false

No overlap because intervals are half-open.

Insert interval.

Step	Events
After insertion	[(10, 20), (20, 30)]

Return:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) search + O(n) insertion	Binary search finds position quickly, list insertion may shift elements
Space	O(n)	Store all successful bookings

The binary search portion is efficient and requires only logarithmic time. However, arrays and slices require shifting elements during insertion, which costs linear time in the worst case.

Since at most 1000 bookings exist, this complexity is easily acceptable.

Test Cases

# Provided example
calendar = MyCalendar()
assert calendar.book(10, 20) is True      # First booking succeeds
assert calendar.book(15, 25) is False     # Overlaps existing booking
assert calendar.book(20, 30) is True      # Boundary touch is allowed

# Empty calendar booking
calendar = MyCalendar()
assert calendar.book(5, 10) is True       # Insert into empty calendar

# Non-overlapping intervals
calendar = MyCalendar()
assert calendar.book(1, 5) is True
assert calendar.book(5, 10) is True
assert calendar.book(10, 15) is True

# Complete overlap
calendar = MyCalendar()
assert calendar.book(10, 20) is True
assert calendar.book(10, 20) is False     # Exact same interval

# Interval inside another interval
calendar = MyCalendar()
assert calendar.book(10, 30) is True
assert calendar.book(15, 20) is False

# Interval containing another interval
calendar = MyCalendar()
assert calendar.book(15, 20) is True
assert calendar.book(10, 30) is False

# Overlap on left side
calendar = MyCalendar()
assert calendar.book(10, 20) is True
assert calendar.book(5, 15) is False

# Overlap on right side
calendar = MyCalendar()
assert calendar.book(10, 20) is True
assert calendar.book(15, 25) is False

# Large values
calendar = MyCalendar()
assert calendar.book(0, 1_000_000_000) is True
assert calendar.book(999_999_999, 1_000_000_000) is False

# Sparse intervals
calendar = MyCalendar()
assert calendar.book(1, 2) is True
assert calendar.book(100, 200) is True
assert calendar.book(50, 60) is True

Test	Why
Provided example	Validates standard overlapping behavior
Empty calendar booking	Ensures initialization works correctly
Boundary touching intervals	Confirms half-open interval handling
Exact same interval	Detects direct overlap
Nested interval	Detects containment overlap
Containing interval	Detects reverse containment
Left-side overlap	Validates overlap from earlier interval
Right-side overlap	Validates overlap from later interval
Large values	Confirms large integer handling
Sparse intervals	Ensures insertion ordering works

Edge Cases

Boundary-touching intervals

One of the most common mistakes is incorrectly treating [10, 20) and [20, 30) as overlapping.

Because the intervals are half-open, the value 20 belongs only to the second interval. The implementation correctly handles this by checking:

previousEnd > startTime

rather than:

previousEnd >= startTime

This subtle distinction ensures adjacent intervals are allowed.

Complete containment

A booking may be fully inside another interval, such as booking [15, 20) after [10, 30) already exists.

A naive implementation that only checks matching start times could miss this case. The overlap condition properly identifies containment because:

30 > 15

which correctly signals overlap.

Insertion at beginning or end

When inserting a new interval at the start or end of the sorted list, one neighboring interval does not exist.

This can easily cause index-out-of-bounds errors if boundary conditions are not handled carefully.

The implementation explicitly checks:

if index > 0

before accessing the previous interval, and:

if index < len(self.events)

before accessing the next interval.

This guarantees safe handling of edge insertions.