My Calendar [1:3]

 booking 문제.

 

My Calendar 1: leetcode.com/problems/my-calendar-i/

My Calendar I - LeetCode

 

class MyCalendar {
public:
    vector<vector<int>> reserves;
    
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        for(auto reserve : reserves){
            int oldStart = reserve[0];
            int oldEnd = reserve[1];
            
            if(start >= oldStart && start < oldEnd){
                return false;
            }
            
            if(oldStart < end && oldEnd >= end){
                return false;
            }    
            
            if(oldStart >= start && oldEnd < end){
                return false;
            }
        }
        reserves.push_back({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);
 */

-bruteforcing

Time complexity: O(N^2)

Space complexity: O(N)

 

-> 조건식을 최적화하면 (oldStart < end && oldEnd > start)가 된다.

 

class Node {
public:
    int start;
    int end;
    
    Node * left = NULL;
    Node * right = NULL;
    
    Node(int start, int end){
        this->start = start;
        this->end = end;
    }
};

class MyCalendar {
public:
    Node * root = NULL;
    
    MyCalendar() {
        
    }
    
    bool insert(Node * node, int start, int end){
        if(end <= node->start){
            if(node->left == NULL){
                node->left = new Node(start, end);
                return true;
            }
            return insert(node->left, start, end);
        }
        
        if(node->end <= start){
            if(node->right == NULL){
                node->right = new Node(start, end);
                return true;
            }
            return insert(node->right, start, end);
        }
        return false;
    }
    
    bool book(int start, int end) {
        if(root == NULL){
            root = new Node(start, end);
            return true;
        }
        
        return insert(this->root, start, end);
    }
};

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

-insert into tree

Time complexity: O(log N) -> It is not a balance tree.  worst case: O(N) in skewed tree

Space complexity: O(N)

 

 

My Calendar 2: leetcode.com/problems/my-calendar-ii/

My Calendar II - LeetCode

 

class MyCalendarTwo {
public:
    vector<pair<int,int>> overlaps;
    vector<pair<int,int>> calendar;
    MyCalendarTwo() {
        
    }
    
    bool book(int start, int end) {
        for(auto overlap : overlaps){
            int i = overlap.first;
            int j = overlap.second;
            
            if(j > start && i < end){
                return false;
            }
        }
        
        for(auto v : calendar){
            int i = v.first;
            int j = v.second;
            
            if(j > start && i < end){
                overlaps.push_back(make_pair(max(i, start), min(j, end)));
            }
        }
        calendar.push_back(make_pair(start, end));
        return true;
    }
};

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

Time complexity: O(N^2)

Space complexity: O(N)

 

class MyCalendarTwo {
public:
    map<int, int> m;
    MyCalendarTwo() {
        
    }
    
    bool book(int start, int end) {
        m[start] += 1;
        m[end] -= 1;
        
        int active = 0;
        
        for(auto v : m){
            int d = v.second;
            active += d;
            
            if(active >= 3){
                m[start] -= 1;
                m[end] += 1;
                return false;
            }
        }
        return true;
    }
};

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

 start를 1 더하고 end -1 더해서 active로 3개가 겹치는지 확인하는 훌륭한 해답이다.  

Time complexity: O(N^2 * log N)

Space complexity: O(N)

 

 

My Calendar 3: leetcode.com/problems/my-calendar-iii/

My Calendar III - LeetCode

class MyCalendarThree {
public:
    map<int, int> m;
    MyCalendarThree() {
        
    }
    
    int book(int start, int end) {
        m[start] += 1;
        m[end] -= 1;
        
        int ret = 0;
        int active = 0;
        for(auto v :  m){
            active += v.second;
            ret = max(active, ret);
        }
        return ret;
    }
};

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

Time complexity: O(N^2)

Space complexity: O(N)