731. 我的日程安排表 II
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。
请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例：
MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true 解释： 前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。 第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。 第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。 第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订； 时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。
提示：
MyCalendar.book 函数最多不超过 1000次。MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。原站题解
javascript 解法, 执行用时: 39 ms, 内存消耗: 58.4 MB, 提交时间: 2025-01-03 09:12:48
var MyCalendarTwo = function() {
this.booked = [];
this.overlaps = [];
};
MyCalendarTwo.prototype.book = function(start, end) {
for (const arr of this.overlaps) {
let l = arr[0], r = arr[1];
if (l < end && start < r) {
return false;
}
}
for (const arr of this.booked) {
let l = arr[0], r = arr[1];
if (l < end && start < r) {
this.overlaps.push([Math.max(l, start), Math.min(r, end)]);
}
}
this.booked.push([start, end]);
return true;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* var obj = new MyCalendarTwo()
* var param_1 = obj.book(start,end)
*/
javascript 解法, 执行用时: 414 ms, 内存消耗: 74.6 MB, 提交时间: 2025-01-03 09:12:32
var MyCalendarTwo = function() {
this.tree = new Map();
};
MyCalendarTwo.prototype.book = function(start, end) {
const update = (start, end, val, l, r, idx) => {
if (r < start || end < l) {
return;
}
if (!this.tree.has(idx)) {
this.tree.set(idx, [0, 0]);
}
if (start <= l && r <= end) {
this.tree.get(idx)[0] += val;
this.tree.get(idx)[1] += val;
} else {
const mid = (l + r) >> 1;
update(start, end, val, l, mid, 2 * idx);
update(start, end, val, mid + 1, r, 2 * idx + 1);
if (!this.tree.has(2 * idx)) {
this.tree.set(2 * idx, [0, 0]);
}
if (!this.tree.has(2 * idx + 1)) {
this.tree.set(2 * idx + 1, [0, 0]);
}
this.tree.get(idx)[0] = this.tree.get(idx)[1] + Math.max(this.tree.get(2 * idx)[0], this.tree.get(2 * idx + 1)[0]);
}
}
update(start, end - 1, 1, 0, 1000000000, 1);
if (!this.tree.has(1)) {
this.tree.set(1, [0, 0])
}
if (this.tree.get(1)[0] > 2) {
update(start, end - 1, -1, 0, 1000000000, 1);
return false;
}
return true;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* var obj = new MyCalendarTwo()
* var param_1 = obj.book(start,end)
*/
java 解法, 执行用时: 397 ms, 内存消耗: 54.6 MB, 提交时间: 2025-01-03 09:12:16
class MyCalendarTwo {
Map<Integer, int[]> tree;
public MyCalendarTwo() {
tree = new HashMap<Integer, int[]>();
}
public boolean book(int start, int end) {
update(start, end - 1, 1, 0, 1000000000, 1);
tree.putIfAbsent(1, new int[2]);
if (tree.get(1)[0] > 2) {
update(start, end - 1, -1, 0, 1000000000, 1);
return false;
}
return true;
}
public void update(int start, int end, int val, int l, int r, int idx) {
if (r < start || end < l) {
return;
}
tree.putIfAbsent(idx, new int[2]);
if (start <= l && r <= end) {
tree.get(idx)[0] += val;
tree.get(idx)[1] += val;
} else {
int mid = (l + r) >> 1;
update(start, end, val, l, mid, 2 * idx);
update(start, end, val, mid + 1, r, 2 * idx + 1);
tree.putIfAbsent(2 * idx, new int[2]);
tree.putIfAbsent(2 * idx + 1, new int[2]);
tree.get(idx)[0] = tree.get(idx)[1] + Math.max(tree.get(2 * idx)[0], tree.get(2 * idx + 1)[0]);
}
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
java 解法, 执行用时: 286 ms, 内存消耗: 45.1 MB, 提交时间: 2025-01-03 09:12:05
class MyCalendarTwo {
TreeMap<Integer, Integer> cnt;
public MyCalendarTwo() {
cnt = new TreeMap<Integer, Integer>();
}
public boolean book(int start, int end) {
int ans = 0;
int maxBook = 0;
cnt.put(start, cnt.getOrDefault(start, 0) + 1);
cnt.put(end, cnt.getOrDefault(end, 0) - 1);
for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
int freq = entry.getValue();
maxBook += freq;
ans = Math.max(maxBook, ans);
if (maxBook > 2) {
cnt.put(start, cnt.getOrDefault(start, 0) - 1);
cnt.put(end, cnt.getOrDefault(end, 0) + 1);
return false;
}
}
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
java 解法, 执行用时: 62 ms, 内存消耗: 44.7 MB, 提交时间: 2025-01-03 09:11:50
class MyCalendarTwo {
List<int[]> booked;
List<int[]> overlaps;
public MyCalendarTwo() {
booked = new ArrayList<int[]>();
overlaps = new ArrayList<int[]>();
}
public boolean book(int start, int end) {
for (int[] arr : overlaps) {
int l = arr[0], r = arr[1];
if (l < end && start < r) {
return false;
}
}
for (int[] arr : booked) {
int l = arr[0], r = arr[1];
if (l < end && start < r) {
overlaps.add(new int[]{Math.max(l, start), Math.min(r, end)});
}
}
booked.add(new int[]{start, end});
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/
cpp 解法, 执行用时: 642 ms, 内存消耗: 299.5 MB, 提交时间: 2025-01-03 09:11:31
// 线段树
class MyCalendarTwo {
public:
MyCalendarTwo() {
}
void update(int start, int end, int val, int l, int r, int idx) {
if (r < start || end < l) {
return;
}
if (start <= l && r <= end) {
tree[idx].first += val;
tree[idx].second += val;
} else {
int mid = (l + r) >> 1;
update(start, end, val, l, mid, 2 * idx);
update(start, end, val, mid + 1, r, 2 * idx + 1);
tree[idx].first = tree[idx].second + max(tree[2 * idx].first, tree[2 * idx + 1].first);
}
}
bool book(int start, int end) {
update(start, end - 1, 1, 0, 1e9, 1);
if (tree[1].first > 2) {
update(start, end - 1, -1, 0, 1e9, 1);
return false;
}
return true;
}
private:
unordered_map<int, pair<int, int>> tree;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo* obj = new MyCalendarTwo();
* bool param_1 = obj->book(start,end);
*/
cpp 解法, 执行用时: 129 ms, 内存消耗: 43.2 MB, 提交时间: 2025-01-03 09:11:07
// 差分数组
class MyCalendarTwo {
public:
MyCalendarTwo() {
}
bool book(int start, int end) {
int ans = 0;
int maxBook = 0;
cnt[start]++;
cnt[end]--;
for (auto &[_, freq] : cnt) {
maxBook += freq;
ans = max(maxBook, ans);
if (maxBook > 2) {
cnt[start]--;
cnt[end]++;
return false;
}
}
return true;
}
private:
map<int, int> cnt;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo* obj = new MyCalendarTwo();
* bool param_1 = obj->book(start,end);
*/
cpp 解法, 执行用时: 19 ms, 内存消耗: 38.6 MB, 提交时间: 2025-01-03 09:10:40
// 直接遍历
class MyCalendarTwo {
public:
MyCalendarTwo() {
}
bool book(int start, int end) {
for (auto &[l, r] : overlaps) {
if (l < end && start < r) {
return false;
}
}
for (auto &[l, r] : booked) {
if (l < end && start < r) {
overlaps.emplace_back(max(l, start), min(r, end));
}
}
booked.emplace_back(start, end);
return true;
}
private:
vector<pair<int, int>> booked;
vector<pair<int, int>> overlaps;
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo* obj = new MyCalendarTwo();
* bool param_1 = obj->book(start,end);
*/
golang 解法, 执行用时: 248 ms, 内存消耗: 10.7 MB, 提交时间: 2022-11-21 10:12:34
type pair struct{ first, second int }
type MyCalendarTwo map[int]pair
func Constructor() MyCalendarTwo {
return MyCalendarTwo{}
}
func (tree MyCalendarTwo) update(start, end, val, l, r, idx int) {
if r < start || end < l {
return
}
if start <= l && r <= end {
p := tree[idx]
p.first += val
p.second += val
tree[idx] = p
return
}
mid := (l + r) >> 1
tree.update(start, end, val, l, mid, 2*idx)
tree.update(start, end, val, mid+1, r, 2*idx+1)
p := tree[idx]
p.first = p.second + max(tree[2*idx].first, tree[2*idx+1].first)
tree[idx] = p
}
func (tree MyCalendarTwo) Book(start, end int) bool {
tree.update(start, end-1, 1, 0, 1e9, 1)
if tree[1].first > 2 {
tree.update(start, end-1, -1, 0, 1e9, 1)
return false
}
return true
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 2496 ms, 内存消耗: 25.7 MB, 提交时间: 2022-11-21 10:11:35
class MyCalendarTwo:
def __init__(self):
self.tree = {}
def update(self, start: int, end: int, val: int, l: int, r: int, idx: int) -> None:
if r < start or end < l:
return
if start <= l and r <= end:
p = self.tree.get(idx, [0, 0])
p[0] += val
p[1] += val
self.tree[idx] = p
return
mid = (l + r) // 2
self.update(start, end, val, l, mid, 2 * idx)
self.update(start, end, val, mid + 1, r, 2 * idx + 1)
p = self.tree.get(idx, [0, 0])
p[0] = p[1] + max(self.tree.get(2 * idx, (0,))[0], self.tree.get(2 * idx + 1, (0,))[0])
self.tree[idx] = p
def book(self, start: int, end: int) -> bool:
self.update(start, end - 1, 1, 0, 10 ** 9, 1)
if self.tree[1][0] > 2:
self.update(start, end - 1, -1, 0, 10 ** 9, 1)
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)
python3 解法, 执行用时: 1940 ms, 内存消耗: 16.4 MB, 提交时间: 2022-11-21 10:11:18
from sortedcontainers import SortedDict
class MyCalendarTwo:
def __init__(self):
self.cnt = SortedDict()
def book(self, start: int, end: int) -> bool:
self.cnt[start] = self.cnt.get(start, 0) + 1
self.cnt[end] = self.cnt.get(end, 0) - 1
maxBook = 0
for c in self.cnt.values():
maxBook += c
if maxBook > 2:
self.cnt[start] = self.cnt.get(start, 0) - 1
self.cnt[end] = self.cnt.get(end, 0) + 1
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)
golang 解法, 执行用时: 272 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:10:55
// 差分数组
type MyCalendarTwo struct {
*redblacktree.Tree
}
func Constructor() MyCalendarTwo {
return MyCalendarTwo{redblacktree.NewWithIntComparator()}
}
func (c MyCalendarTwo) add(key, value int) {
if v, ok := c.Get(key); ok {
c.Put(key, v.(int)+value)
} else {
c.Put(key, value)
}
}
func (c MyCalendarTwo) Book(start, end int) bool {
c.add(start, 1)
c.add(end, -1)
maxBook := 0
it := c.Iterator()
for it.Next() {
maxBook += it.Value().(int)
if maxBook > 2 {
c.add(start, -1)
c.add(end, 1)
return false
}
}
return true
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
golang 解法, 执行用时: 60 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:10:17
type pair struct{ start, end int }
type MyCalendarTwo struct{ booked, overlaps []pair }
func Constructor() MyCalendarTwo {
return MyCalendarTwo{}
}
func (c *MyCalendarTwo) Book(start, end int) bool {
for _, p := range c.overlaps {
if p.start < end && start < p.end {
return false
}
}
for _, p := range c.booked {
if p.start < end && start < p.end {
c.overlaps = append(c.overlaps, pair{max(p.start, start), min(p.end, end)})
}
}
c.booked = append(c.booked, pair{start, end})
return true
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
python3 解法, 执行用时: 356 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-21 10:07:44
class MyCalendarTwo:
def __init__(self):
self.booked = []
self.overlaps = []
def book(self, start: int, end: int) -> bool:
if any(s < end and start < e for s, e in self.overlaps):
return False
for s, e in self.booked:
if s < end and start < e:
self.overlaps.append((max(s, start), min(e, end)))
self.booked.append((start, end))
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)