729. 我的日程安排表 I
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。
实现 MyCalendar 类：
MyCalendar() 初始化日历对象。boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 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 <= 109book 方法的次数最多不超过 1000 次。原站题解
javascript 解法, 执行用时: 87 ms, 内存消耗: 62.7 MB, 提交时间: 2025-01-02 09:21:18
var MyCalendar = function() {
this.tree = new Set();
this.lazy = new Set();
};
MyCalendar.prototype.book = function(start, end) {
if (this.query(start, end - 1, 0, 1000000000, 1)) {
return false;
}
this.update(start, end - 1, 0, 1000000000, 1);
return true;
};
MyCalendar.prototype.query = function(start, end, l, r, idx) {
if (start > r || end < l) {
return false;
}
/* 如果该区间已被预订，则直接返回 */
if (this.lazy.has(idx)) {
return true;
}
if (start <= l && r <= end) {
return this.tree.has(idx);
} else {
const mid = (l + r) >> 1;
if (end <= mid) {
return this.query(start, end, l, mid, 2 * idx);
} else if (start > mid) {
return this.query(start, end, mid + 1, r, 2 * idx + 1);
} else {
return this.query(start, end, l, mid, 2 * idx) | this.query(start, end, mid + 1, r, 2 * idx + 1);
}
}
}
MyCalendar.prototype.update = function(start, end, l, r, idx) {
if (r < start || end < l) {
return;
}
if (start <= l && r <= end) {
this.tree.add(idx);
this.lazy.add(idx);
} else {
const mid = (l + r) >> 1;
this.update(start, end, l, mid, 2 * idx);
this.update(start, end, mid + 1, r, 2 * idx + 1);
this.tree.add(idx);
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* var obj = new MyCalendar()
* var param_1 = obj.book(start,end)
*/
javascript 解法, 执行用时: 51 ms, 内存消耗: 58 MB, 提交时间: 2025-01-02 09:20:53
var MyCalendar = function() {
this.booked = [];
};
MyCalendar.prototype.book = function(start, end) {
for (const arr of this.booked) {
let l = arr[0], r = arr[1];
if (l < end && start < r) {
return false;
}
}
this.booked.push([start, end]);
return true;
};
/**
* Your MyCalendar object will be instantiated and called as such:
* var obj = new MyCalendar()
* var param_1 = obj.book(start,end)
*/
cpp 解法, 执行用时: 35 ms, 内存消耗: 42 MB, 提交时间: 2025-01-02 09:20:30
class MyCalendar {
vector<pair<int, int>> booked;
public:
bool book(int start, int end) {
for (auto &[l, r] : booked) {
if (l < end && start < r) {
return false;
}
}
booked.emplace_back(start, end);
return true;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/
cpp 解法, 执行用时: 5 ms, 内存消耗: 43.1 MB, 提交时间: 2025-01-02 09:20:17
class MyCalendar {
set<pair<int, int>> booked;
public:
bool book(int start, int end) {
auto it = booked.lower_bound({end, 0});
if (it == booked.begin() || (--it)->second <= start) {
booked.emplace(start, end);
return true;
}
return false;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/
cpp 解法, 执行用时: 405 ms, 内存消耗: 173 MB, 提交时间: 2025-01-02 09:19:47
class MyCalendar {
unordered_set<int> tree, lazy;
public:
bool query(int start, int end, int l, int r, int idx) {
if (r < start || end < l) {
return false;
}
/* 如果该区间已被预订，则直接返回 */
if (lazy.count(idx)) {
return true;
}
if (start <= l && r <= end) {
return tree.count(idx);
}
int mid = (l + r) >> 1;
return query(start, end, l, mid, 2 * idx) ||
query(start, end, mid + 1, r, 2 * idx + 1);
}
void update(int start, int end, int l, int r, int idx) {
if (r < start || end < l) {
return;
}
if (start <= l && r <= end) {
tree.emplace(idx);
lazy.emplace(idx);
} else {
int mid = (l + r) >> 1;
update(start, end, l, mid, 2 * idx);
update(start, end, mid + 1, r, 2 * idx + 1);
tree.emplace(idx);
if (lazy.count(2 * idx) && lazy.count(2 * idx + 1)) {
lazy.emplace(idx);
}
}
}
bool book(int start, int end) {
if (query(start, end - 1, 0, 1e9, 1)) {
return false;
}
update(start, end - 1, 0, 1e9, 1);
return true;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/
java 解法, 执行用时: 99 ms, 内存消耗: 46.8 MB, 提交时间: 2025-01-02 09:19:18
// 线段树
class MyCalendar {
Set<Integer> tree;
Set<Integer> lazy;
public MyCalendar() {
tree = new HashSet<Integer>();
lazy = new HashSet<Integer>();
}
public boolean book(int start, int end) {
if (query(start, end - 1, 0, 1000000000, 1)) {
return false;
}
update(start, end - 1, 0, 1000000000, 1);
return true;
}
public boolean query(int start, int end, int l, int r, int idx) {
if (start > r || end < l) {
return false;
}
/* 如果该区间已被预订，则直接返回 */
if (lazy.contains(idx)) {
return true;
}
if (start <= l && r <= end) {
return tree.contains(idx);
} else {
int mid = (l + r) >> 1;
if (end <= mid) {
return query(start, end, l, mid, 2 * idx);
} else if (start > mid) {
return query(start, end, mid + 1, r, 2 * idx + 1);
} else {
return query(start, end, l, mid, 2 * idx) | query(start, end, mid + 1, r, 2 * idx + 1);
}
}
}
public void update(int start, int end, int l, int r, int idx) {
if (r < start || end < l) {
return;
}
if (start <= l && r <= end) {
tree.add(idx);
lazy.add(idx);
} else {
int mid = (l + r) >> 1;
update(start, end, l, mid, 2 * idx);
update(start, end, mid + 1, r, 2 * idx + 1);
tree.add(idx);
}
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
java 解法, 执行用时: 25 ms, 内存消耗: 44.7 MB, 提交时间: 2025-01-02 09:18:40
// 二分查找
class MyCalendar {
TreeSet<int[]> booked;
public MyCalendar() {
booked = new TreeSet<int[]>((a, b) -> a[0] - b[0]);
}
public boolean book(int start, int end) {
if (booked.isEmpty()) {
booked.add(new int[]{start, end});
return true;
}
int[] tmp = {end, 0};
int[] arr = booked.ceiling(tmp);
int[] prev = arr == null ? booked.last() : booked.lower(arr);
if (arr == booked.first() || booked.lower(tmp)[1] <= start) {
booked.add(new int[]{start, end});
return true;
}
return false;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
java 解法, 执行用时: 88 ms, 内存消耗: 44.6 MB, 提交时间: 2025-01-02 09:18:13
// 直接遍历
class MyCalendar {
List<int[]> booked;
public MyCalendar() {
booked = new ArrayList<int[]>();
}
public boolean book(int start, int end) {
for (int[] arr : booked) {
int l = arr[0], r = arr[1];
if (l < end && start < r) {
return false;
}
}
booked.add(new int[]{start, end});
return true;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
golang 解法, 执行用时: 144 ms, 内存消耗: 7.6 MB, 提交时间: 2022-11-21 10:04:57
type MyCalendar struct {
tree, lazy map[int]bool
}
func Constructor() MyCalendar {
return MyCalendar{map[int]bool{}, map[int]bool{}}
}
func (c MyCalendar) query(start, end, l, r, idx int) bool {
if r < start || end < l {
return false
}
if c.lazy[idx] { // 如果该区间已被预订，则直接返回
return true
}
if start <= l && r <= end {
return c.tree[idx]
}
mid := (l + r) >> 1
return c.query(start, end, l, mid, 2*idx) ||
c.query(start, end, mid+1, r, 2*idx+1)
}
func (c MyCalendar) update(start, end, l, r, idx int) {
if r < start || end < l {
return
}
if start <= l && r <= end {
c.tree[idx] = true
c.lazy[idx] = true
} else {
mid := (l + r) >> 1
c.update(start, end, l, mid, 2*idx)
c.update(start, end, mid+1, r, 2*idx+1)
c.tree[idx] = true
if c.lazy[2*idx] && c.lazy[2*idx+1] {
c.lazy[idx] = true
}
}
}
func (c MyCalendar) Book(start, end int) bool {
if c.query(start, end-1, 0, 1e9, 1) {
return false
}
c.update(start, end-1, 0, 1e9, 1)
return true
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 940 ms, 内存消耗: 19.7 MB, 提交时间: 2022-11-21 10:04:04
class MyCalendar:
def __init__(self):
self.tree = set()
self.lazy = set()
def query(self, start: int, end: int, l: int, r: int, idx: int) -> bool:
if r < start or end < l:
return False
if idx in self.lazy: # 如果该区间已被预订，则直接返回
return True
if start <= l and r <= end:
return idx in self.tree
mid = (l + r) // 2
return self.query(start, end, l, mid, 2 * idx) or \
self.query(start, end, mid + 1, r, 2 * idx + 1)
def update(self, start: int, end: int, l: int, r: int, idx: int) -> None:
if r < start or end < l:
return
if start <= l and r <= end:
self.tree.add(idx)
self.lazy.add(idx)
else:
mid = (l + r) // 2
self.update(start, end, l, mid, 2 * idx)
self.update(start, end, mid + 1, r, 2 * idx + 1)
self.tree.add(idx)
if 2 * idx in self.lazy and 2 * idx + 1 in self.lazy:
self.lazy.add(idx)
def book(self, start: int, end: int) -> bool:
if self.query(start, end - 1, 0, 10 ** 9, 1):
return False
self.update(start, end - 1, 0, 10 ** 9, 1)
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
python3 解法, 执行用时: 224 ms, 内存消耗: 16.3 MB, 提交时间: 2022-11-21 10:02:51
from sortedcontainers import SortedDict
class MyCalendar:
def __init__(self):
self.booked = SortedDict()
def book(self, start: int, end: int) -> bool:
i = self.booked.bisect_left(end)
if i == 0 or self.booked.items()[i - 1][1] <= start:
self.booked[start] = end
return True
return False
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
golang 解法, 执行用时: 60 ms, 内存消耗: 7.1 MB, 提交时间: 2022-11-21 10:01:55
type MyCalendar struct {
*redblacktree.Tree
}
func Constructor() MyCalendar {
t := redblacktree.NewWithIntComparator()
t.Put(math.MaxInt32, nil) // 哨兵，简化代码
return MyCalendar{t}
}
func (c MyCalendar) Book(start, end int) bool {
node, _ := c.Ceiling(end)
it := c.IteratorAt(node)
if !it.Prev() || it.Value().(int) <= start {
c.Put(start, end)
return true
}
return false
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
golang 解法, 执行用时: 68 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:00:23
type pair struct{ start, end int }
type MyCalendar []pair
func Constructor() MyCalendar {
return MyCalendar{}
}
func (c *MyCalendar) Book(start, end int) bool {
for _, p := range *c {
if p.start < end && start < p.end {
return false
}
}
*c = append(*c, pair{start, end})
return true
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 680 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-21 10:00:06
class MyCalendar:
def __init__(self):
self.booked = []
def book(self, start: int, end: int) -> bool:
if any(l < end and start < r for l, r in self.booked):
return False
self.booked.append((start, end))
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)