目录
- 题目要求
- 思路一：差分数组
-
- 思路二：线段树【先放放，单独学完回来尝试自己套】
-
- 总结
题目要求
思路一：差分数组
- 一个比较简答粗暴的想法，用一个差分数组记录当前日程，在日程开始时间自增一，结束时间自减一。
Java
class MyCalendarThree {
private TreeMap cnt;
public MyCalendarThree() {
cnt = new TreeMap();
}
public int book(int start, int end) {
int res = 0;
int maxBook = 0;
cnt.put(start, cnt.getOrDefault(start, 0) + 1);
cnt.put(end, cnt.getOrDefault(end, 0) - 1);
for(Map.Entry entry : cnt.entrySet()) {
int freq = entry.getValue();
maxBook += freq;
res = Math.max(maxBook, res);
}
return res;
}
}
- 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
- 空间复杂度：
O
(
n
)
O(n)
O(n)
C++
class MyCalendarThree {
map cnt;
public:
MyCalendarThree() {}
int book(int start, int end) {
int res = 0;
int maxBook = 0;
cnt[start]++;
cnt[end]--;
for(auto &[_, freq] : cnt) {
maxBook += freq;
res = max(maxBook, res);
}
return res;
}
};
- 时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)
- 空间复杂度：
O
(
n
)
O(n)
O(n)
思路二：线段树【先放放，单独学完回来尝试自己套】
Java
- 时间复杂度：
O
(
log
n
)
O(log n)
O(logn)
- 空间复杂度：
O
(
m
log
n
)
O(mlog n)
O(mlogn)
C++
- 时间复杂度：
O
(
log
n
)
O(log n)
O(logn)
- 空间复杂度：
O
(
m
log
n
)
O(mlog n)
O(mlogn)
总结
看到这区间就意识到了事情的不对，果然是老朋友线段树了。来拔个flag，搞搞线段树。
