Three different ways


  • 0
    I

    O(n^2)

    class MyCalendar {
        vector<pair<int, int>> intervals;
    public:
        MyCalendar() {
            
        }
        
        bool overlap(pair<int, int> p, int s, int e) {
            return s < p.second && e > p.first;
        }
        
        bool book(int start, int end) {
            for (auto& p : intervals) if (overlap(p, start, end)) return false;
            intervals.push_back({start, end});
            return true;
        }
    };
    

    O(nlogn)
    Find the first end bigger than the current start:

    class MyCalendar {
        map<int, int> m;
    public:
        MyCalendar() {
            
        }
        
        bool book(int start, int end) {
            auto it = m.upper_bound(start);
            if (it == m.end()) {
                m.insert(it == m.begin() ? it : --it, {end, start}); // m.insert({end, start}) also works. Use iterator as a hint can make insertion faster?
                return true;
            } else {
                if (end > it->second) return false;
                else {
                    m.insert(it == m.begin() ? it : --it, {end, start});
                    return true;
                }
            }
        }
    };
    

    O(nlogn)

    Find the first start bigger than the current end:

    class MyCalendar {
        map<int, int> m;
    public:
        MyCalendar() {
            
        }
        
        bool book(int start, int end) {
            auto it = m.lower_bound(end);
            if (it != m.begin()) --it;
            else {
                m.insert(it, {start, end}); // m.insert({start, end}) also works. Use iterator as a hint can make insertion faster?
                return true;
            }
            if (it->second > start) return false;
            else {
                m.insert(it, {start, end});
                return true;
            }
        }
    };
    

Log in to reply
 

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