729. 我的日程安排表 I
题目描述
设计日程类 MyCalendar。每个日程用半开区间 [startTime, endTime) 表示，即包含所有满足 startTime <= x < endTime 的时刻 x。
MyCalendar()：创建一个空日历。
book(startTime, endTime)：尝试加入一个日程。如果它和已加入的某个日程有共同时刻，就是冲突，此时不加入并返回 false；否则加入日历并返回 true。
因为是半开区间，一个日程的结束时刻等于另一个的开始时刻时不算冲突。
示例 1
输入：操作 = ["MyCalendar","book","book","book"], 参数 = [[],[10,20],[15,25],[20,30]] 输出：[null,true,false,true]
解释：[15,25) 与 [10,20) 重叠被拒；[20,30) 只在端点 20 处相接，可以加入。
数据范围
0 <= start < end <= 10^9- 每组测试中
book最多被调用1000次。
解题思路：直接遍历
把成功的预订存在列表里。新区间 [start, end) 与已有区间 [s, e) 相交，当且仅当 s < end 且 start < e。遍历所有已有预订，只要碰到一个相交就拒绝；全部不相交才加入。
为什么正确
列表中的区间两两不相交。
复杂度分析
第 n 次调用 O(n)，总计 O(n²)；空间 O(n)。用有序结构二分可以做到单次 O(log n)。
易错点
区间是半开的，判断相交必须用严格小于：[10,20) 和 [20,30) 只是相接。只检查新区间的端点是否落在旧区间内是不够的，还会漏掉新区间完全包住旧区间的情况。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class MyCalendar:
def __init__(self):
self.booked = []
def book(self, startTime: int, endTime: int) -> bool:
for s, e in self.booked:
if s < endTime and startTime < e:
return False
self.booked.append((startTime, endTime))
return Trueclass MyCalendar {
private List<int[]> booked;
public MyCalendar() {
booked = new ArrayList<>();
}
public boolean book(int startTime, int endTime) {
for (int[] b : booked) {
if (b[0] < endTime && startTime < b[1]) {
return false;
}
}
booked.add(new int[]{startTime, endTime});
return true;
}
}class MyCalendar {
public:
vector<pair<int, int>> booked;
MyCalendar() {
booked.clear();
}
bool book(int startTime, int endTime) {
for (auto& [s, e] : booked) {
if (s < endTime && startTime < e) {
return false;
}
}
booked.push_back({startTime, endTime});
return true;
}
};type MyCalendar struct {
booked [][2]int
}
func Constructor() MyCalendar {
return MyCalendar{}
}
func (this *MyCalendar) Book(startTime int, endTime int) bool {
for _, b := range this.booked {
if b[0] < endTime && startTime < b[1] {
return false
}
}
this.booked = append(this.booked, [2]int{startTime, endTime})
return true
}var MyCalendar = function() {
this.booked = [];
};
MyCalendar.prototype.book = function(startTime, endTime) {
for (const [s, e] of this.booked) {
if (s < endTime && startTime < e) {
return false;
}
}
this.booked.push([startTime, endTime]);
return true;
};class MyCalendar {
booked: number[][];
constructor() {
this.booked = [];
}
book(startTime: number, endTime: number): boolean {
for (const [s, e] of this.booked) {
if (s < endTime && startTime < e) {
return false;
}
}
this.booked.push([startTime, endTime]);
return true;
}
}其他解法
直接遍历代码最短，调用次数少时足够；有序集合 + 二分查找只检查两个邻居，调用次数多时明显更快。
解法 2：有序集合 + 二分查找 时间 O(n log n)，空间 O(n)
已预订的区间互不重叠，按起点排序后终点也有序。新区间 [s, e) 只可能和两个邻居冲突：起点不小于 s 的第一个区间，需要它的起点 ≥ e；它前面的一个区间，需要它的终点 ≤ s。二分找到位置后检查这两个邻居，都不冲突就插入。
C++ 和 Java 用平衡树（map、TreeMap），单次是 O(log n)。Python、Go、JS 用有序数组，查找 O(log n)，插入要搬移元素，最坏 O(n)，但常数很小。
from bisect import bisect_left
class MyCalendar:
def __init__(self):
self.starts = []
self.ends = []
def book(self, startTime: int, endTime: int) -> bool:
k = bisect_left(self.starts, startTime)
if k < len(self.starts) and self.starts[k] < endTime:
return False
if k > 0 and self.ends[k - 1] > startTime:
return False
self.starts.insert(k, startTime)
self.ends.insert(k, endTime)
return Trueclass MyCalendar {
private TreeMap<Integer, Integer> booked;
public MyCalendar() {
booked = new TreeMap<>();
}
public boolean book(int startTime, int endTime) {
Map.Entry<Integer, Integer> next = booked.ceilingEntry(startTime);
if (next != null && next.getKey() < endTime) return false;
Map.Entry<Integer, Integer> prev = booked.lowerEntry(startTime);
if (prev != null && prev.getValue() > startTime) return false;
booked.put(startTime, endTime);
return true;
}
}class MyCalendar {
public:
map<int, int> booked;
MyCalendar() {
}
bool book(int startTime, int endTime) {
auto it = booked.lower_bound(startTime);
if (it != booked.end() && it->first < endTime) return false;
if (it != booked.begin() && prev(it)->second > startTime) return false;
booked[startTime] = endTime;
return true;
}
};type MyCalendar struct {
starts []int
ends []int
}
func Constructor() MyCalendar {
return MyCalendar{}
}
func (this *MyCalendar) Book(startTime int, endTime int) bool {
k := sort.SearchInts(this.starts, startTime)
if k < len(this.starts) && this.starts[k] < endTime {
return false
}
if k > 0 && this.ends[k-1] > startTime {
return false
}
this.starts = append(this.starts, 0)
copy(this.starts[k+1:], this.starts[k:])
this.starts[k] = startTime
this.ends = append(this.ends, 0)
copy(this.ends[k+1:], this.ends[k:])
this.ends[k] = endTime
return true
}var MyCalendar = function() {
this.starts = [];
this.ends = [];
};
MyCalendar.prototype.book = function(startTime, endTime) {
let lo = 0, hi = this.starts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.starts[mid] < startTime) lo = mid + 1;
else hi = mid;
}
if (lo < this.starts.length && this.starts[lo] < endTime) return false;
if (lo > 0 && this.ends[lo - 1] > startTime) return false;
this.starts.splice(lo, 0, startTime);
this.ends.splice(lo, 0, endTime);
return true;
};class MyCalendar {
starts: number[];
ends: number[];
constructor() {
this.starts = [];
this.ends = [];
}
book(startTime: number, endTime: number): boolean {
let lo = 0, hi = this.starts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.starts[mid] < startTime) lo = mid + 1;
else hi = mid;
}
if (lo < this.starts.length && this.starts[lo] < endTime) return false;
if (lo > 0 && this.ends[lo - 1] > startTime) return false;
this.starts.splice(lo, 0, startTime);
this.ends.splice(lo, 0, endTime);
return true;
}
}