0729. 我的日程安排表 I【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力遍历

1. 📝 题目描述

• leetcode

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订。

日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为， startTime <= x < endTime。

实现 MyCalendar 类：

• MyCalendar() 初始化日历对象。
• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20，且不包含时间 20。

---

提示：

• 0 <= start < end <= 10^9
• 每个测试用例，调用 book 方法的次数最多不超过 1000 次。

2. 🎯 s.1 - 暴力遍历

c

typedef struct {
    int starts[1000];
    int ends[1000];
    int size;
} MyCalendar;

MyCalendar* myCalendarCreate() {
    MyCalendar* obj = (MyCalendar*)calloc(1, sizeof(MyCalendar));
    return obj;
}

bool myCalendarBook(MyCalendar* obj, int start, int end) {
    for (int i = 0; i < obj->size; i++) {
        if (start < obj->ends[i] && end > obj->starts[i]) return false;
    }
    obj->starts[obj->size] = start;
    obj->ends[obj->size] = end;
    obj->size++;
    return true;
}

void myCalendarFree(MyCalendar* obj) {
    free(obj);
}

js

var MyCalendar = function () {
  this.events = []
}

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
  for (const [s, e] of this.events) {
    if (start < e && end > s) return false
  }
  this.events.push([start, end])
  return true
}

py

class MyCalendar:
    def __init__(self):
        self.events = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.events:
            if start < e and end > s:
                return False
        self.events.append((start, end))
        return True

• 时间复杂度：book $O(n)$，其中 n 是已预订事件数
• 空间复杂度：$O(n)$

算法思路：

• 用数组存储所有已预订的区间 [start, end)
• 每次预订时遍历检查是否与已有区间重叠（start < e && end > s）
• 无重叠则加入数组并返回 true