当前位置:网站首页>Sword finger offer II 058: schedule
Sword finger offer II 058: schedule
2022-07-05 06:09:00 【Chrysanthemum headed bat】
The finger of the sword Offer II 058: calendar
subject
Topic linking
Please implement a MyCalendar
Class to store your schedule . If there is no other schedule for the time to be added , You can store this new schedule .
MyCalendar
There is one book(int start, int end)
Method . It means in start To end Add a schedule in time , Be careful , The time here is a half open interval , namely [start, end)
, The set of real Numbers x
For the range of , start <= x < end
.
When there is some time overlap between the two schedules ( For example, both schedules are in the same time ), There will be repeat bookings .
Every time you call MyCalendar.book
When the method is used , If the schedule can be successfully added to the calendar without causing duplicate bookings , return true
. otherwise , return false
And don't add the schedule to the calendar .
Please follow the steps below to call MyCalendar
class : MyCalendar cal = new MyCalendar();
MyCalendar.book(start, end)
Example :
Input :
["MyCalendar","book","book","book"]
[[],[10,20],[15,25],[20,30]]
Output : [null,true,false,true]
explain :
MyCalendar myCalendar = new MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false , The second schedule cannot be added to the calendar , Because of time 15 It has been scheduled by the first schedule
MyCalendar.book(20, 30); // returns true , The third schedule can be added to the calendar , Because the first schedule doesn't include time 20
Problem solving
Method 1 :map+ Two points search
because map Will automatically key Sort , So sort the left boundary directly .
Find... By bisection , Find greater than or equal to end, The left border .
Just make , The right boundary ratio of the previous one start Small can be inserted successfully
class MyCalendar {
public:
map<int,int> mp;
MyCalendar() {
}
bool book(int start, int end) {
map<int,int>::iterator it=mp.lower_bound(end);// return key value Greater than or equal to end The first position
if(it==mp.begin()||(--it)->second<=start){
mp[start]=end;
return true;
}
return false;
}
};
边栏推荐
猜你喜欢
从Dijkstra的图灵奖演讲论科技创业者特点
shared_ Repeated release heap object of PTR hidden danger
网络工程师考核的一些常见的问题:WLAN、BGP、交换机
Navicat連接Oracle數據庫報錯ORA-28547或ORA-03135
可变电阻器概述——结构、工作和不同应用
MatrixDB v4.5.0 重磅发布,全新推出 MARS2 存储引擎!
做 SQL 性能优化真是让人干瞪眼
R language [import and export of dataset]
1.15 - 输入输出系统
Doing SQL performance optimization is really eye-catching
随机推荐
Sqlmap tutorial (II) practical skills I
Over fitting and regularization
LeetCode 1200.最小绝对差
CPU内核和逻辑处理器的区别
A reason that is easy to be ignored when the printer is offline
One question per day 2047 Number of valid words in the sentence
可变电阻器概述——结构、工作和不同应用
SPI details
1041 Be Unique
2017 USP Try-outs C. Coprimes
【Rust 笔记】16-输入与输出(上)
927. 三等分 模拟
R language [import and export of dataset]
6. Logistic model
MIT-6874-Deep Learning in the Life Sciences Week 7
数据可视化图表总结(一)
leetcode-556:下一个更大元素 III
【Rust 笔记】13-迭代器(下)
[rust notes] 16 input and output (Part 1)
1040 Longest Symmetric String