当前位置:网站首页>【729. 我的日程安排表 I】
【729. 我的日程安排表 I】
2022-07-05 16:13:00 【千北@】
来源:力扣(LeetCode)
描述:
实现一个 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 <= 109
- 每个测试用例,调用 book 方法的次数最多不超过 1000 次。
方法一:直接遍历
我们记录下所有已经预订的课程安排区间,当我们预订新的区间 [start,end)
时,此时检查当前已经预订的每个日程安排是否与新日程安排冲突。若不冲突,则可以添加新的日程安排。
- 对于两个区间 [s1, e1)和 [s2, e2),如果二者没有交集,则此时应当满足 s1 ≥ e2 或者 s2 ≥ e1,这就意味着如果满足 s1 < e2 并且 s2 < e1 ,则两者会产生交集。
代码:
class MyCalendar {
private:
vector<pair<int, int>> booked;
public:
MyCalendar() {
}
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;
}
};
执行用时:80 ms, 在所有 C++ 提交中击败了77.49%的用户
内存消耗:36.6 MB, 在所有 C++ 提交中击败了97.08%的用户
复杂度分析
时间复杂度:O(n2), 其中 n 表示日程安排的数量。由于每次在进行预订时,都需要遍历所有已经预订的行程安排。
空间复杂度: O(n),其中 n 表示日程安排的数量。需要保存所有已经预订的行程。
方法二:二分查找
如果我们按时间顺序维护日程安排,则可以通过二分查找日程安排的情况来检查新日程安排是否可以预订,若可以预订则在排序结构中更新插入日程安排。
- 需要一个数据结构能够保持元素排序和支持快速插入,可以用
TreeSet
来构建。对于给定的区间[start,end)
,我们每次查找起点大于等于end
的第一个区间 [ l1, r1 ),同时紧挨着 [ l1, r1) 的前一个区间为 [ l2, r2),此时如果满足 r2 ≤ start < end ≤ l1 ,则该区间可以预订。
代码:
class MyCalendar {
private:
set<pair<int, int>> booked;
public:
MyCalendar() {
}
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;
}
};
执行用时:64 ms, 在所有 C++ 提交中击败了98.77%的用户
内存消耗:37.9 MB, 在所有 C++ 提交中击败了53.51%的用户
复杂度分析
时间复杂度: O(nlogn), 其中 n 表示日程安排的数量。由于每次在进行预订时,都需要进行二分查找,需要的时间为 O(logn)。
空间复杂度: O(n),其中 n 表示日程安排的数量。需要保存所有已经预订的行程。
方法三:线段树
代码:
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;
}
};
执行用时:476 ms, 在所有 C++ 提交中击败了5.03%的用户
内存消耗:171.4 MB, 在所有 C++ 提交中击败了7.53%的用户
边栏推荐
- Flet tutorial 12 stack overlapping to build a basic introduction to graphic and text mixing (tutorial includes source code)
- Jarvis OJ 简单网管协议
- Jarvis OJ Webshell分析
- Clear restore the scene 31 years ago, volcanic engine ultra clear repair beyond classic concert
- Google Earth Engine(GEE)——Kernel核函数简单介绍以及灰度共生矩阵
- [61dctf]fm
- PSPNet | 语义分割及场景分析
- 【 brosser le titre 】 chemise culturelle de l'usine d'oies
- 不敢买的思考
- [61dctf]fm
猜你喜欢
How to set the WiFi password of the router on the computer
Jarvis OJ Flag
Scratch colorful candied haws Electronic Society graphical programming scratch grade examination level 3 true questions and answers analysis June 2022
Starkware: to build ZK "universe"
Binary tree related OJ problems
有序链表集合求交集 方法 总结
单商户 V4.4,初心未变,实力依旧!
养不起真猫,就用代码吸猫 -Unity 粒子实现画猫咪
数据访问 - EntityFramework集成
Flet教程之 12 Stack 重叠组建图文混合 基础入门(教程含源码)
随机推荐
sqlserver 做cdc 要对数据库性能有什么要求么
极坐标扇图使用场景与功能详解
为季前卡牌游戏 MotoGP Ignition Champions 做好准备!
Fleet tutorial 09 basic introduction to navigationrail (tutorial includes source code)
scratch五彩糖葫芦 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
Cartoon: what is the eight queens problem?
DeSci:去中心化科学是Web3.0的新趋势?
【深度学习】深度学习如何影响运筹学?
Dare not buy thinking
Solution of vant tabbar blocking content
帮忙看看是什么问题可以吗?[ERROR] Could not execute SQL stateme
EDI许可证和ICP经营性证有什么区别
數據訪問 - EntityFramework集成
Cartoon: what is service fusing?
新春限定丨“牛年忘烦”礼包等你来领~
Today's sleep quality record 79 points
二叉树相关OJ题
DenseNet
Apple 已弃用 NavigationView,使用 NavigationStack 和 NavigationSplitView 实现 SwiftUI 导航
Google Earth Engine(GEE)——Kernel核函数简单介绍以及灰度共生矩阵