自学做网站可以赚钱吗,wordpress andriod,廊坊网站建设咨询青橙网络,制作二维码的思维导图文章目录1. 题目2. 解题2.1 set 二分查找2.2 差分思想1. 题目
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时#xff0c;则可以存储这个新的日程安排。
MyCalendar 有一个 book(int start, int end)方法。 它意味着在 start 到 end 时间…
文章目录1. 题目2. 解题2.1 set 二分查找2.2 差分思想1. 题目
实现一个 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]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/my-calendar-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 set 二分查找
类似题目 LeetCode 729. 我的日程安排表 Iset 二分查找 LeetCode 732. 我的日程安排表 III差分思想
class MyCalendarTwo {setpairint, int s;//区间setpairint, int intersection;//区间交集
public:MyCalendarTwo() {intersection.insert({INT_MAX, INT_MAX});intersection.insert({INT_MIN, INT_MIN});//加入边界简化代码}bool book(int start, int end) {auto it intersection.lower_bound({start,end});if(it-first end)//当前跟交集是否相交return false;if((--it)-second start)//前面跟交集是否相交return false;for(auto it1 s.begin(); it1 ! s.end(); it1)//跟区间是否相交{if(it1-first end it1-second start)intersection.insert({max(it1-first, start), min(it1-second, end)});// 相交加入交集}s.insert({start, end});return true; }
};280 ms 32.2 MB
2.2 差分思想
对上一题通用把3改成2即可
class MyCalendarTwo {mapint,int m;
public:MyCalendarTwo() {}bool book(int start, int end) {m[start];//差分思想m[end]--;int count 0;for(auto it m.begin(); it ! m.end(); it){count it-second;if(count 3)//重叠3次了{m[start]--;//恢复原状m[end];return false;}}return true;}
};664 ms 35.8 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
