一台vps可以做几个网站,购物网站的提交订单功能需要做唯一性约束,潜江市建设工程合同备案网站,南阳做网站优化的公司本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 实现一个 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]。 解法1 直接遍历
记录下所有已经预定的课程安排区间与已经预定过两次的课程安排区间当我们预定新的区间 [ s t a r t , e n d ) [start, end) [start,end) 时此时检查当前已经预定过两次的每个日程安排是否与新日程安排冲突。若不冲突则可以添加新的日程安排。
对于两个区间 [ s 1 , e 1 ) [s_1, e_1) [s1,e1) 和 [ s 2 , e 2 ) [s_2, e_2) [s2,e2) 如果二者没有交集则此时应当满足 s 1 ≥ e 2 s_1 \ge e_2 s1≥e2 或者 s 2 ≥ e 1 s_2 \ge e_1 s2≥e1 这就意味着如果满足 s 1 e 2 s_1 e_2 s1e2 并且 s 2 e 1 s_2 e_1 s2e1 。首先检测新加入的区间 [ s t a r t , e n d ) [start, end) [start,end)是否与已经预定过两次的区间有交集如果没有冲突则将新加入的区间与已经预定的区间进行检查求出新增的预定两次的区间。对于两个区间 [ s 1 , e 1 ) [s_1, e_1) [s1,e1) 和 [ s 2 , e 2 ) [s_2,e_2) [s2,e2) 则他们之间的交集为 [ max ( s 1 , s 2 ) , min ( e 1 , e 2 ) ) [\max(s_1,s_2), \min(e_1,e_2)) [max(s1,s2),min(e1,e2))
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:vectorpairint, int booked;vectorpairint, int overlaps;
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) 其中 n n n 表示日程安排的数量。由于每次在进行预订时都需要遍历所有已经预订的行程安排。空间复杂度 O ( n ) O(n) O(n) 其中 n n n 表示日程安排的数量。需要保存所有已经预订的行程。 解法2 差分数组
利用差分数组的思想每当我们预定一个新的日程安排 [ s t a r t , e n d ) [start, end) [start,end)在 s t a r t start start 计数 c n t [ s t a r t ] cnt[start] cnt[start] 加 1 1 1 表示从 s t a r t start start 预定的数目加 1 1 1 从 e n d end end 计数 c n t [ e n d ] cnt[end] cnt[end] 减 1 1 1 表示从 e n d end end 开始预定的数目减 1 1 1 。此时以起点 x x x 开始的预定的数目 book x ∑ y ≤ x cnt [ y ] \textit{book}_x \sum_{y \le x}\textit{cnt}[y] bookx∑y≤xcnt[y] 当我们将 [ s t a r t , e n d ) [start, end) [start,end) 加入后如果发现存在区间的预定数目大于 2 2 2 时此时为非法应去除新加入的区间 [ s t a r t , e n d ) [start, end) [start,end) 。由于本题中 start , end \textit{start}, \textit{end} start,end 数量较大我们利用 TreeMap \texttt{TreeMap} TreeMap 计数即可。
class MyCalendarTwo {
public:MyCalendarTwo() {}bool book(int start, int end) {int maxBook 0;cnt[start];--cnt[end];for (auto [_, freq] : cnt) {maxBook freq;if (maxBook 2) {--cnt[start];cnt[end];return false;}}return true;}
private:mapint, int cnt;
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) 其中 n n n 为日程安排的数量。每次求的最大的预定需要遍历所有的日程安排。空间复杂度 O ( n ) O(n) O(n) 其中 n n n 为日程安排的数量。需要空间存储所有的日程安排计数需要的空间为 O ( n ) O(n) O(n) 。 解法3 线段树
利用线段树假设我们开辟了数组 arr [ 0 , ⋯ , 1 0 9 ] \textit{arr}[0,\cdots, 10^9] arr[0,⋯,109] 初始时每个元素的值都为 0 0 0 对于每次行程预定的区间 [ s t a r t , e n d ) [start, end) [start,end) 则我们将区间中的元素 arr [ start , ⋯ , end − 1 ] \textit{arr}[\textit{start},\cdots,\textit{end}-1] arr[start,⋯,end−1] 中的每个元素加 1 1 1 如果数组 a r r arr arr 的最大元素大于 2 2 2 时此时则出现某个区间被安排了 2 2 2 次上此时返回 false \texttt{false} false 同时将数组区间 arr [ start , ⋯ , end − 1 ] \textit{arr}[\textit{start},\cdots,\textit{end}-1] arr[start,⋯,end−1] 进行减 1 1 1 即可恢复。
实际我们不必实际开辟数组 arr \textit{arr} arr 可采用动态线段树懒标记 lazy \textit{lazy} lazy 标记区间 [ l , r ] [l,r] [l,r] 进行累加的次数 tree \textit{tree} tree 记录区间 [ l , r ] [l,r] [l,r] 的最大值每次动态更新线段树即可。
class MyCalendarTwo {
public:MyCalendarTwo() {}void update(int s, int e, int val, int l, int r, int idx) {if (r s || l e) return;if (s l r e) {tree[idx].first val;tree[idx].second val;} else {int mid (l r) 1;update(s, e, val, l, mid, 2 * idx);update(s, e, 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_mapint, pairint, int tree;
};复杂度分析
时间复杂度 O ( n log C ) O(n \log C) O(nlogC) 其中 n n n 为日程安排的数量。由于使用了线段树查询线段树的最大深度为 log C \log C logC 每次最多会查询 log C \log C logC 个节点每次求最大的预定需的时间复杂度为 O ( log C log C ) O(\log C \log C) O(logClogC) 因此时间复杂度为 O ( n log C ) O(n \log C) O(nlogC) 在此 C C C 取固定值即为 1 0 9 10^9 109空间复杂度 O ( n log C ) O(n \log C) O(nlogC) 其中 n n n 为日程安排的数量。由于该解法采用的为动态线段树线段树的最大深度为 log C \log C logC 每次预定最多会在线段树上增加 log C \log C logC 个节点因此空间复杂度为 O ( n log C ) O(n \log C) O(nlogC) 在此 C C C 取固定值即为 1 0 9 10^9 109
