LeetCode 解題筆記：729. My Calendar I

作者：王一哲
日期：2026年9月12日


LeetCode 題目連結：729. My Calendar I

解題想法

中等難度題，題目給一個 class 部分的程式碼，及一個包含行程開始、結束時間的串列，要求我們完成 class 之中的函式 book，於函式中先檢查這個行程是否與原有行程時間重複，如果重複回傳 False；如果不重複，更新資料並回傳 True。

由於這題的測資不多，可以用一層 for 迴圈逐一檢查新的時間 $startTime$ 及 $endTime$ 是否與原有行程重疊。如果想要再更快速一點，可以用字典儲存每一個排入的行程開始時刻及對應的結束時刻，再用另一個陣列 $starts$ 儲存行程開始時間，並用二分搜尋法找新的時間 $startTime$ 於 $starts$ 之中插入的索引值，檢查 $startTime$ 及 $endTime$ 是否與前、後的行程重疊。

Python 程式碼

Runtime: 179 ms, beats 50.25%. Memory: 20.30 MB, beats 24.38%.

class MyCalendar:
    def __init__(self):
        self.intervals = []  # (start, end)

    def book(self, startTime: int, endTime: int) -> bool:
        # 逐一檢查時間時否重疊
        for s, e in self.intervals:
            if startTime < e and endTime > s:
                return False
        self.intervals.append((startTime, endTime))
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

Runtime: 19 ms, beats 98.17%. Memory: 20.17 MB, beats 58.06%.

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.intervals = dict()  # start: end
        self.starts = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 用二分搜尋法找 starts 之中插入 startTime 的右側位置
        idx = bisect_left(self.starts, startTime)
        # 前面有別的行程，檢查時間是否重疊
        if idx > 0:
            prev_end = self.intervals[self.starts[idx - 1]]
            if startTime < prev_end:
                return False
        # 後面有別的行程，檢查時間是否重疊
        if idx < len(self.starts):
            next_start = self.starts[idx]
            if endTime > next_start:
                return False
        # 於 starts 之中插入新資料並保持排序
        self.intervals[startTime] = endTime
        self.starts.insert(idx, startTime)
        return True


# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

C++ 程式碼

Runtime: 19 ms, beats 98.95%. Memory: 42.79 MB, beats 99.95%.

class MyCalendar {
private:
    vector<pair<int, int>> intervals;

public:
    MyCalendar() {
        intervals.clear();
    }
    
    bool book(int startTime, int endTime) {
        for(auto it : intervals) {
            if (startTime < it.second && endTime > it.first) {
                return false;
            }
        }
        intervals.push_back(make_pair(startTime, endTime));
        return true;
    }
};

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

Runtime: 19 ms, beats 58.95%. Memory: 44.52MB, beats 21.27%.

class MyCalendar {
private:
    map<int, int> intervals;
    vector<int> starts;

public:
    MyCalendar() {
        intervals.clear();
        starts.clear();
    }
    
    bool book(int startTime, int endTime) {
        // 用二分搜尋法找 starts 之中插入 startTime 的右側位置
        int idx = upper_bound(starts.begin(), starts.end(), startTime) - starts.begin();
        // 前面有別的行程，檢查時間是否重疊
        if (idx > 0) {
            int prev_end = intervals[starts[idx - 1]];
            if (startTime < prev_end) {
                return false;
            }
        }
        // 後面有別的行程，檢查時間是否重疊
        if (idx < (int)starts.size()) {
            int next_start = starts[idx];
            if (endTime > next_start) {
                return false;
            }
        }
        // 於 starts 之中插入新資料並保持排序
        starts.insert(starts.begin() + idx, startTime);
        intervals[startTime] = endTime;
        return true;
    }
};

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