Leetcode 729. My Calendar I

Arunima Mandal

Problem Link: https://leetcode.com/problems/my-calendar-i/description/

Note:

This problem is interesting to solve. It’s easy but again if you want to optimize, you will have to be careful about using data structure.

Approach 1: Using vector and Binary Search (O(N^2logN) time complexity)

In this approach, the time complexity is O(N^2 logN) because the sort() function takes O(NlogN) time. So for calling it N times, the time complexity will be O(N*NlogN) = O(N^2logN).

class MyCalendar {
public:
    vector<pair<int,int> > v;
    
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        return true; 
    }
};

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

Approach 2: Using Set and Binary Search (O(NlogN) time complexity)

Here, the highest time is taken by the set insert which is logN. So for calling it N times, the time complexity will be O(N*logN) = O(NlogN).

class MyCalendar {
public:
    //vector<pair<int,int> > v;
    set<pair<int,int> >st;
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        pair<int,int> p{start,end};
        /*
        int l=lower_bound(v.begin(), v.end(), p)-v.begin();
        if(l<v.size() && (start==v[l].first || end>v[l].first) || (l>=1 && start<v[l-1].second)) return false;
        else if(l==v.size() && l>=1 && start<v[l-1].second) return false;   

        v.push_back({start,end});
        sort(v.begin(), v.end());
        */
        auto nextEvent=st.lower_bound(p);
        if(nextEvent!=st.end() && end>nextEvent->first) return false;
        if(nextEvent!=st.begin())
        {
            auto prevEvent=prev(nextEvent);
            if(start<prevEvent->second) return false;
        }
        st.insert(p);
        return true;
    }
};

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

Leave a comment