O(log n) Check just one element in the map and not 2


  • 1
    D

    Observation is that if you store the elements in the map by end and not start, one can always query for the lower bound of the incoming interval's start timestamp, and check if this new interval overlaps with any interval already in the map which ends just at or after the new interval's start timestamp. If there is no overlap, then the existing interval will start strictly after the new interval (to be inserted) ends.

    class MyCalendar {
        map<int, int> meetings;
        
        bool canBook(int start, int end) {
            --end;
            auto it = meetings.lower_bound(start);
            if (it == meetings.end()) return true;
            const auto itStart = it->second;
            const auto itEnd = it->first;
            // There is no overlap if the new interval ends before the existing interval begins
            return end < itStart;
        }
    public:
        MyCalendar() { }
    
        bool book(int start, int end) {
            if (start == end) return true;
            if (canBook(start, end)) {
                meetings.insert(make_pair(end-1, start));
                return true;
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.