732. My Calendar III (prev)
Implement a MyCalendarThree
class to store your events. A new event can always be added.
Your class will have one method, book(int start, int end)
. Formally, this represents a booking on the half open interval [start, end)
, the range of real numbers x
such that start <= x < end
.
A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)
For each call to the method MyCalendar.book
, return an integer K
representing the largest integer such that there exists a K
-booking in the calendar.
Your class will be called like this: MyCalendarThree cal = new MyCalendarThree();
MyCalendarThree.book(start, end)
Example 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation:
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.
Note:
- The number of calls to
MyCalendarThree.book
per test case will be at most400
. - In calls to
MyCalendarThree.book(start, end)
,start
andend
are integers in the range[0, 10^9]
.
Approach #1: C++.
class MyCalendarThree {
public:
MyCalendarThree() { } int book(int start, int end) {
++books[start];
--books[end];
int count = 0;
int ant = 0;
for (auto it : books) {
count += it.second;
ant = max(ant, count);
if (it.first > end) break;
}
maxNum = max(maxNum, ant);
return maxNum;
} private:
map<int, int> books;
int maxNum = 0;
};
Approach #2: C++.
class MyCalendarThree {
public:
MyCalendarThree() {
books[INT_MAX] = 0;
books[INT_MIN] = 0;
maxCount = 0;
} int book(int start, int end) {
auto l = prev(books.upper_bound(start));
auto r = books.lower_bound(end); for (auto curr = l, next = curr; curr != r; curr = next) {
++next;
if (next->first > end)
books[end] = curr->second;
if (curr->first <= start && next->first > start) {
maxCount = max(maxCount, books[start] = curr->second+1);
}
else {
maxCount = max(maxCount, ++curr->second);
}
}
return maxCount;
} private:
map<int, int> books;
int maxCount;
};
Note:
Approach #3: C++. [segment tree]
...........
最新文章
- Lucene提供的条件判断查询
- PHP图像处理之画图
- Linux使用笔记: 定制core dump文件的文件名
- 邮件Mail
- Android设计模式系列--工厂方法模式
- BZOJ 2257: [Jsoi2009]瓶子和燃料 裴蜀定理
- c++ 派生类向基类转换的可访问性
- VS中调用SQL SERVER存储过程
- 20162330 实验四 《Android程序设计》 实验报告
- 【bzoj1045】【HAOI2008】 糖果传递
- unix的发展
- Linux 一块网卡配置多个IP的方法
- Leetcode 11.盛最多水的容器 By Python
- shell脚本作为cgi程序--以web版man为例
- vs2013中将原来在iis express中的网站转到iis中时,报“无法在web服务器上调试”的解决方法
- hdu 5014 异或序列
- linux环境下mysql默认是区分表名大小写的
- MySQL三层逻辑架构
- Python实例---抽屉热搜榜前端代码分析
- ubuntu 16.04 镜像下载
热门文章
- VM tools安装错误The path ";"; is not a valid path to the xx generic kernel headers.
- nvl()与regexp_replace()
- 如何在Mac的Finder中显示/usr、/tmp、/var等隐藏目录
- python增删改查zabbix主机等
- WebStorm中SVN配置
- Maven项目中使用JUnit进行单元测试
- java数据的5种存储位置(转)
- hdu1085Holding Bin-Laden Captive!组合问题
- listen 72
- pod lib lint 报错 Unable to find a specification for `AMap2DMap` depended upon by `DingtalkPod