# Leetcode 解題速記 729. My Calendar I
###### tags: `LeetCode` `C++`
題敘:
---
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.

Example 1:

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

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

測資範圍:
---
* `0 <= start < end <= 109`
* At most `1000` calls will be made to book.

解題筆記:
---
這題的解法主要是要觀察新的booking中start與end的數字，是否與已經存在的booking有衝突。

這次我選擇使用vector of pair去儲存已經存在的booking，每讀取一次新的booking資料，就先traverse過一次已經存在的booking。

比較的方式也不難，這邊使用了max與min函式，比較的時候只要確定兩個booking中最大的起始時間不要小於最小的結束時間，就不會發生重疊的問題。

能夠這樣判斷的原因在於，兩個booking中最大的start，一定屬於時間排序上比較晚的那個booking，同時，兩個booking中最小的那個end，也一定屬於時間排序上比較早的那個booking，這樣比較的意義就是在確保較晚booking的開頭不會重疊到較早booking的結尾。

程式碼:
---

class MyCalendar {
public:
    vector<pair<int, int>> booking;
    MyCalendar()
    {
    }
    bool book(int start, int end)
    {
        for (auto temp : booking)
        {
            if (max(temp.first, start) < min(temp.second, end))
            {
                return false;
            }
        }
        booking.push_back({start, end});
        return true;
    }
};