# LeetCode 729. My Calendar I

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

## 題目大意

實作一個日曆，如果新增的事件不會導致二次預約的話，可以新增事件

定義二次預約為：發生在兩個事件存在非空的交集 (即兩個事件間有某段時間重疊)

每個事件可以用一對整數 `start` 和 `end` 表示，代表一個預訂的區間 `[start, end)`

***

`MyCalendar` 類別：

- `MyCalendar()` 初始化日曆物件。
- `boolean book(int start, int end)` 如果能成功將事件新增至日曆且不會導致二次預約，則回傳 `true`；否則回傳 `false`

## 思考

我們這邊使用 `map` 來建立`end` 對 `start` 的映射

接著我們使用 `upper_bound()` 找到第一個事件滿足該事件的 key 值 (`end`) 嚴格大於新增事件的 `start`
白話講就如其名，我們找一個上界，這個上界我們希望它會是排在新增事件後的事件

接著我們要檢查新增事件會不會跟該上界有重疊，兩種情況不會：

1. `it == events.end()` 表示目前新增事件開始後，沒有事件已開始且尚未結束 (不存在事件的 `end` 嚴格大於新增事件的 `start`)
2. `it->second >= end` 如果存在事件 `it` 的 `end` 嚴格大於新增事件的 `start` ，非二次預約的情況應該是 `it` 要發生在新增事件之後，也就是其 `start` (`it->second`) 要不小於新增事件的 `end`

如果可以新增該事件，就加入該事件並回傳 `true`

class MyCalendar
{
public:
    MyCalendar() {}

    bool book(int start, int end)
    {
        auto it = events.upper_bound(start);
        if (it == events.end() || it->second >= end)
        {
            events[end] = start;
            return true;
        }
        return false;
    }

private:
    map<int, int> events;
};

簡單，交卷