Problem

You are implementing a program to use as your calendar. Events can be added to the calendar when they don't overlap.

Events are represented by a pair of integers on the half-open interval [start, end) and the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

• MyCalendar() initializes the calendar object
• boolean book(int start, int end) returns true if the event can be added to the calendar without overlap or false otherwise

Source: https://leetcode.com/problems/my-calendar-i

Constraints

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

Asymptotic Complexity

• Time: O(logn) to search an ordered map with upper_bound
• Space: O(n) one record per range added to the calendar

Strategy

Store the ranges in an ordered map using end values as the key. Search for conflicts by finding the next record ending after the current start time via upper_bound. Then:

• Add if there is no such record
• Add if a record is found and it starts on-or-after the current end time
• Otherwise, don't add because there is an overlap

Implementation

class MyCalendar {
public:
    MyCalendar() = default;
    bool book(int start, int end) {
        auto itr = _calendar.upper_bound(start); 
        if (itr == _calendar.end() || itr->second >= end) {
            _calendar.insert({end, start});
            return true;
        }

        return false;
    }

private:
    map<int, int> _calendar;
};