当前位置:网站首页>【729. 我的日程安排錶 I】
【729. 我的日程安排錶 I】
2022-07-05 16:49: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%的用戶
边栏推荐
- [深度学习][原创]让yolov6-0.1.0支持yolov5的txt读取数据集模式
- Cartoon: what is MapReduce?
- Combined use of vant popup+ other components and pit avoidance Guide
- Quelques réflexions cognitives
- Android 隐私沙盒开发者预览版 3: 隐私安全和个性化体验全都要
- 【深度学习】深度学习如何影响运筹学?
- Intel 13th generation Raptor Lake processor information exposure: more cores, larger cache
- 详解SQL中Groupings Sets 语句的功能和底层实现逻辑
- [vulnerability warning] cve-2022-26134 conflict Remote Code Execution Vulnerability POC verification and repair process
- [echart] resize lodash to realize chart adaptation when window is zoomed
猜你喜欢
How to set the WiFi password of the router on the computer
Detailed explanation of use scenarios and functions of polar coordinate sector diagram
新春限定丨“牛年忘烦”礼包等你来领~
Solve cmakelist find_ Package cannot find Qt5, ECM cannot be found
Benji Bananas 会员通行证持有人第二季奖励活动更新一览
Win11 prompt: what if the software cannot be downloaded safely? Win11 cannot download software safely
Jarvis OJ shell流量分析
Today's sleep quality record 79 points
Keras crash Guide
Win11如何给应用换图标?Win11给应用换图标的方法
随机推荐
Apple has abandoned navigationview and used navigationstack and navigationsplitview to implement swiftui navigation
Detailed explanation of use scenarios and functions of polar coordinate sector diagram
清晰还原31年前现场,火山引擎超清修复Beyond经典演唱会
Global Data Center released DC brain system, enabling intelligent operation and management through science and technology
【 brosser le titre 】 chemise culturelle de l'usine d'oies
Data verification before and after JSON to map -- custom UDF
Benji Banas membership pass holders' second quarter reward activities update list
PHP 严格模式
怎样在电脑上设置路由器的WiFi密码
数据访问 - EntityFramework集成
How does win11 change icons for applications? Win11 method of changing icons for applications
Google Earth engine (GEE) -- a brief introduction to kernel kernel functions and gray level co-occurrence matrix
Jarvis OJ 简单网管协议
How to set the WiFi password of the router on the computer
养不起真猫,就用代码吸猫 -Unity 粒子实现画猫咪
[team PK competition] the task of this week has been opened | question answering challenge to consolidate the knowledge of commodity details
Games101 notes (II)
Summary of methods for finding intersection of ordered linked list sets
Data access - entityframework integration
SQL injection of cisp-pte (Application of secondary injection)