#729

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

My Calendar I

Implement a calendar supporting non-overlapping event bookings using binary search for efficient insertion and conflict detection.

array binary search design segment tree ordered set

Problem Statement

You are tasked with designing a personal calendar system that allows adding new events while preventing overlapping times. Each event is defined by a start and end time, and it can only be added if it does not intersect any existing events. An event is represented by a half-open interval [start, end), meaning the start time is inclusive and the end time is exclusive.

A double booking occurs when two events share any common time. Your system should efficiently handle a sequence of booking requests and return whether each booking is successful. Constraints include 0 <= start < end <= 10^9 and at most 1000 booking calls, emphasizing the need for efficient insertion and conflict checking.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]] Output [null, true, false, true]

Explanation MyCalendar myCalendar = new MyCalendar(); myCalendar.book(10, 20); // return True myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event. myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints

0 <= start < end <= 109
At most 1000 calls will be made to book.

Solution Approach

Store events in a sorted list

Maintain a list of already booked intervals sorted by start time. This ordering allows using binary search to find where a new event could fit while preserving the sorted property, directly supporting fast conflict checks.

Binary search for insertion

For each booking request, perform a binary search to locate the position where the new interval would be inserted. Check only the neighboring intervals for overlap, leveraging the sorted property to reduce the number of comparisons compared to a linear scan.

Check for conflicts

After finding the insertion point, verify that the new interval does not overlap with the previous or next intervals. If no conflict exists, insert the event and return true; otherwise, reject the booking and return false. This ensures no double booking occurs, enforcing the half-open interval rule.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

Time complexity is O(N log N) due to binary search for each booking in a list of N events. Space complexity is O(N) to store all booked intervals.

What Interviewers Usually Probe

Consider the performance of repeated booking checks and how sorting or search impacts efficiency.
Mention that using a sorted list plus binary search avoids checking all events linearly.
Demonstrate understanding of half-open interval semantics to avoid off-by-one overlap errors.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the half-open interval correctly, allowing end times to conflict with start times.
Performing linear scans for each booking, leading to O(N^2) behavior with many events.
Neglecting to check both neighboring intervals when inserting a new event in the sorted list.

Follow-up variants

Extending to My Calendar II or III, which allow one or multiple overlaps and require interval counting.
Using a balanced binary search tree or segment tree instead of a list for faster dynamic insertions.
Supporting queries for free time slots or event counts within a range instead of single bookings.

FAQ

What is the main strategy to prevent double bookings in My Calendar I?

Use a sorted list of existing intervals and binary search to find the insertion point, then check adjacent intervals for conflicts.

How do half-open intervals affect booking logic?

Half-open intervals [start, end) mean the start time is included but the end is excluded, so two events touching at boundaries do not overlap.

Can we optimize beyond linear scans for this problem?

Yes, binary search over the sorted event list reduces the number of comparisons from O(N) to O(log N) per booking.

What are common mistakes when implementing this calendar?

Ignoring boundary conditions, failing to check both neighbors for overlap, or using inefficient scans for each insertion.

Why is this problem categorized under binary search over valid answer space?

Because each booking requires locating the correct interval position in a sorted list, binary search efficiently determines whether insertion is valid.

terminal

Solution

Solution 1: Ordered Set

We can use an ordered set to store the schedule. An ordered set can perform insert, delete, and search operations in $O(\log n)$ time. The elements in the ordered set are sorted by the $\textit{endTime}$ of the schedule in ascending order.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class MyCalendar:

    def __init__(self):
        self.sd = SortedDict()

    def book(self, start: int, end: int) -> bool:
        idx = self.sd.bisect_right(start)
        if idx < len(self.sd) and self.sd.values()[idx] < end:
            return False
        self.sd[end] = start
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)

Continue Practicing

#731 my calendar ii #732 my calendar iii #493 reverse pairs