C++ std::map lower_bound and upper_bound


  • 0
    B

    complexity is O(log n), which is binary search for lower_bound

    class MyCalendar {
    public:
        map<int,int>mp;
        MyCalendar() {
            
        }
        
        bool book(int start, int end) {
            if(mp.empty())
            {
                mp[start] = end;
                return true;
            }
            
            auto it_start = mp.lower_bound(start);
            if(it_start != mp.begin()) it_start--;
            auto it_end = mp.upper_bound(end);
            while(it_start != it_end)
            {
                if(it_start->first >= start && it_start->first < end) return false;
                if(it_start->first <= start && start < it_start->second) return false;
                it_start++;
            }
            mp[start] = end;
            return true;        
        }
    };
    
    /**
     * Your MyCalendar object will be instantiated and called as such:
     * MyCalendar obj = new MyCalendar();
     * bool param_1 = obj.book(start,end);
     */

Log in to reply
 

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