You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

Your event will be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

  • MyCalendar() Initializes the calendar object.
  • bool book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Examples

Example 1:

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, 25); // 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 <= 10^9
  • At most 1000 calls will be made to book.

Thinking Process

  1. Ordered Set: std::set maintains sorted order automatically
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class MyCalendar {
public:
    MyCalendar() {
        
    }
    
    bool book(int startTime, int endTime) {
        const pair<int, int> event{startTime, endTime};
        const auto nextEvent = calendar.lower_bound(event);
        if(nextEvent != calendar.end() && nextEvent->first < endTime) {
            return false;
        }
        if(nextEvent != calendar.begin()) {
            const auto preEvent = prev(nextEvent);
            if(preEvent->second > startTime) {
                return false;
            }
        }
        calendar.insert(event);
        return true;
    }

private:
    set<pair<int, int>> calendar;
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(startTime,endTime);
 */

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Ordered Set: std::set maintains sorted order automatically

How the code works:

  1. Ordered Set: std::set maintains sorted order automatically
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Algorithm Explanation:

  1. Data Structure: set<pair<int, int>> maintains intervals sorted by start time
    • Automatically sorted by first element (start time)
    • O(log n) insertion and search
  2. book() Method:
    • Find Next Event (Line 8): lower_bound({start, end}) finds first interval with start >= new start
    • Check Next Overlap (Lines 9-11): If next event exists and its start < new end, they overlap
    • Check Previous Overlap (Lines 12-16): If previous event exists and its end > new start, they overlap
    • Insert (Line 17): If no overlaps, insert and return true

Overlap Detection Logic:

For intervals [s1, e1) and [s2, e2) to overlap:

  • Condition: s1 < e2 && s2 < e1

In our code:

  • Next event check: nextEvent->first < endTime means s2 < e1 ✓
  • Previous event check: preEvent->second > startTime means e2 > s1 ✓

Example Walkthrough:

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

Step 1: book(10, 20)
  calendar = {}
  nextEvent = calendar.end() (no next event)
  preEvent check: nextEvent == begin() (no previous)
  Insert: calendar = {(10, 20)}
  Return: true ✓

Step 2: book(15, 25)
  calendar = {(10, 20)}
  nextEvent = lower_bound({15, 25}) = {(10, 20)} (start=10 < 15, but it's the closest)
  Actually, lower_bound finds first with start >= 15, so:
    nextEvent = calendar.end() (no event with start >= 15)
  Wait, let me reconsider...
  
  Actually: lower_bound({15, 25}) in set {(10, 20)}:
    - Compares (15, 25) with (10, 20)
    - Since 15 > 10, it continues
    - Reaches end, so nextEvent = end()
  
  Check next: nextEvent == end() → skip
  Check previous: prev(end()) = {(10, 20)}
    preEvent->second = 20 > 15 = startTime → OVERLAP!
  Return: false ✓

Step 3: book(20, 30)
  calendar = {(10, 20)}
  nextEvent = lower_bound({20, 30}) = end() (no event with start >= 20)
  Check next: skip
  Check previous: prev(end()) = {(10, 20)}
    preEvent->second = 20 > 20 = startTime? No, 20 is not > 20
    So no overlap (half-open: [10, 20) doesn't include 20)
  Insert: calendar = {(10, 20), (20, 30)}
  Return: true ✓

Complexity Analysis:

  • Time Complexity: O(log n) per book() call
    • lower_bound: O(log n)
    • prev(): O(1) for bidirectional iterators
    • insert(): O(log n)
    • Overall: O(log n) per operation
  • Space Complexity: O(n)
    • Store up to n intervals
    • Each interval: O(1) space
    • Overall: O(n)

      Common Mistakes

  1. Empty calendar: First booking always succeeds
  2. Adjacent intervals: [10, 20) and [20, 30) don’t overlap (half-open)
  3. Exact overlap: [10, 20) and [10, 20) overlap
  4. Contained interval: [10, 30) contains [15, 25) → overlap

  5. Large ranges: Handle up to 10^9 values

  6. Inclusive end: Treating end as inclusive instead of exclusive
  7. Wrong overlap check: Not checking both next and previous events
  8. Iterator errors: Not checking end() before dereferencing
  9. Boundary conditions: prev(begin()) is undefined, always check begin() first
  10. Comparison logic: Confusing lower_bound behavior with custom comparators

Key Takeaways

  1. Ordered Set: std::set maintains sorted order automatically
  2. Binary Search: lower_bound efficiently finds insertion point
  3. Half-Open Intervals: End is exclusive, so [10, 20) and [20, 30) don’t overlap
  4. Two Checks: Only need to check next and previous events (at most 2)
  5. Overlap Condition: s1 < e2 && s2 < e1 for intervals [s1, e1) and [s2, e2)

References

Template Reference