Leetcode - 729. My Calendar I

문제

구현문제, [start, end] 시간 예약 함수 book()이 호출될때, 이전 시간과 겹쳐서 예약이 불가능하면 false, 가능하면 true를 리턴하라.

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

해결

밸런스 트리로 구성되어있는 map자료구조 사용.

• upper_bound(n): n보다 큰 값중에 첫번째 iter
• lower_bound(n): n보다 큰거나 같은 값중에 첫번째 iter

               it->second   it->first
 (5)-----(10)      (12)-------(19)      (22)-------(24)
                           (16)-------------(23)
                           start             end

우선 end값을 기준으로 정렬한다. map<end, start> 순서 주의.

그리고 새로 들어온 값의 start를 기준으로 upper_bound(start)를 하면 기존 비교해야할 요소의 iterator가 리턴된다.

가령 위와같이 사전에 시간이 예약되어있을때, 새로운 예약 [16,23]이 들어온다고 해보자. upper_bound(16)을 하면 map의 19 요소가 선택될것이다. 만약 end 값이 기존예약 시작지점인 it->second (12) 보다 작다면 예약은 성공한다.

그런데 만약 새로운 값이 [8,11] 이라면? 위의 조건을 만족하지만 false이어야 한다. 하지만 이 경우 upper_bound(5) 는 [5,10]을 리턴하므로 거기서 다시 계산을 하면 된다. 생각하기 어려웠던 문제였다.

class MyCalendar {
    map<int, int> cal;
public:
    MyCalendar() {
        cal.clear();
    }
    
    bool book(int start, int end) {
        auto it = cal.upper_bound(start);
        if (it == cal.end() || end <= it->second)
            cal[end] = start;
        else
            return false;
        return true;
    }
};

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