My Calendar I


  • 1

    Click here to see the full article post


  • 0
    R

    class MyCalendar {
    public:
    vector<vector<int> > calendar;
    MyCalendar() {

    }
    
    bool book(int start, int end) {
        for(int i = 0; i < calendar.size(); i++){
            if(
                (calendar[i][0] <= start && start < calendar[i][1]) || 
                (calendar[i][0] < end && end <= calendar[i][1]) || 
                (calendar[i][0] >= start && end >= calendar[i][1])
              ){
                return false;
            }
        }
        
        vector<int> interval;
        interval.push_back(start);
        interval.push_back(end);
        
        calendar.push_back(interval);
        
        return true;
    }
    

    };

    /**

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

  • 0

    The complexity analysis of the second solution says insert it in O(1) time. Isn't it O(log N) time?


  • 0
    L

    @awice
    calendar.get(prev) <= start <= end <= next should be calendar.get(prev)) <= start <= end <= calendar.get(next) ? I am not familiar with the Java syntax.


  • 0

    @LeonCheng No. calendar.get(prev) is the end of the previous interval; next is the start of the next interval. calendar.get(x) returns the end of the interval starting at x.


  • 0
    K

    @jianchao.li.fighter I think so. TreeMap is based on red-black tree and the time complexity of insert a event should be O(log N), where N is the number of events booked.


Log in to reply
 

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