Segment Tree-732. My Calendar III
2024-09-26 14:08:46
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.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex> using namespace std; class MyCalendarThree
{
public:
map<int, int> mmp;
MyCalendarThree()
{ } int book(int start, int end)
{
mmp[start]++;
mmp[end]--;
int maxCount = , sum = ;
for (auto a : mmp)
{
sum += a.second;
if (sum > maxCount)
maxCount = sum;
}
return maxCount;
}
};
最新文章
- jQuery的案例及必知重要的jQuery选择器
- [jquery]if条件句
- swift 中数据类型那个的转换
- VS2010添加资源文件
- 笔记 (note)
- iOS button 里边的 字体的 摆放
- [2]. jekyll安装与应用
- centos7开机/etc/rc.local不执行的问题
- word2vec生成词向量原理
- JAVA FILE or I/O学习 - File学习
- Linux目录结构及快捷键
- windows Tomcat+Nginx 集群 迷你版
- echarts legend 重叠 (转载)
- jdbc连接mysql加载驱动程序com.mysql.jdbc.Driver
- Linux kernel的中断子系统之(四):High level irq event handler
- Hexo优化 | 创建sitemap站点地图并向Google提交
- WebPackBrows
- 4.5Python数据类型(5)之列表类型
- Python pip下载安装库 临时用清华镜像命令
- Spring的面向切面
热门文章
- WPF之DataGrid控件根据某列的值设置行的前景色(色
- Gitlab不小心关闭了sign-in,无法登录web的坑。。。
- 神奇的照片修复术,这才是 PS 的正确打开方式!
- AJAX 请求中多出了一次 OPTIONS 请求 导致 Laravel 中间件无法对 Header 传入的 Token 无法获取
- kerberos认证的步骤,学习笔记
- Debian8 下面 muduo库编译与使用
- 2018.09.16 atcoder Garbage Collector(贪心)
- hdu-1143(简单dp)
- python类的继承-1
- BSD Socket (java)