[LeetCode] 729. My Calendar I

https://leetcode.com/problems/my-calendar-i/description/?envType=daily-question&envId=2024-09-26

leetcode - My Calendar I

문제 유형 : 구현, 이진 탐색

문제 난이도 : Medium

 

문제

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

 

캘린더 프로그램을 구현하시오.

시간대 중복이 안되면 새로운 이벤트를 추가할 수 있다.

이벤트는 [start, end)로 주어져서, 반열림 구간으로, start부터 end전날까지로 표현된다.

 

MyCalendar() - calendar 객체 생성

boolean book(int start, int end) - [start, end)구간을 예약한다. 성공 시 true, 실패 시 false 반환.

 

풀이

MyCalendar()의 멤버로 vector<pair<int, int>>로 시작 구간과 끝 구간을 저장한다.

book 기능에는 우선 배열이 비어 있으면, 그냥 추가하고 true를 반환시킨다.

그게 아니라면, 이진 탐색을 이용해서 넣을 자리를 찾는다.

start가 mid의 종료일보다 크거나 같으면 left를 mid+1로, 아니라면 right을 mid로 옮김을 반복한다.

이진탐색 후에, left번째 인덱스에 넣으면 되는데, 

만약 left가 0이거나 start가 left-1의 end보다 크거나 같고, left가 n이거나 end가 기존 left자리 스케줄의 start보다 작으면,

left번째에 삽입하고 true를 반환한다.

그게 아니라면 실패이므로 false를 반환한다.

 

코드

C++

class MyCalendar {
private:
    vector<pair<int, int>> table;
public:
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        int n = table.size();
        
        int left = 0;
        int right = n;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (table[mid].second <= start) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        if ((left == 0 || table[left-1].second <= start) && (left == n || end <= table[left].first)) {
            table.insert(table.begin() + left, {start, end});
            return true;
        }
        
        return false;
    }
};

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