电影采集网站怎么做seo,别人帮做的网站怎么修改,开发一款游戏软件需要多少钱,用树莓派做网站服务器好吗题目链接#xff0c;描述
https://www.lintcode.com/problem/1063
实现一个MyCalendarThree 来储存你的时间。一个新的事件 总是 可以被加入。你的类会有一种方法#xff1a;book(int start, int end)。 正式的说#xff0c;这代表在一个半开区间 [start, end) 上进行预订…题目链接描述
https://www.lintcode.com/problem/1063
实现一个MyCalendarThree 来储存你的时间。一个新的事件 总是 可以被加入。你的类会有一种方法book(int start, int end)。 正式的说这代表在一个半开区间 [start, end) 上进行预订实数x 的范围即 start x end。当K个事件有一个非空交集的时候一个K预订将会发生。即某一个时刻对于K个事件是共用的对于每一个对于方法 MyCalendar.book的调用返回一个整数K代表日历中存在K预订的最大的整数。你的类将会这样被调用: MyCalendarThree cal new MyCalendarThree(); MyCalendarThree.book(start, end)。每个测试用例将会调用 MyCalendarThree.book 至多400次 。
在调用MyCalendarThree.book(start, end)时 start 和 end是在[0, 10^9]内的整数。
样例
样例1输入:
MyCalendarThree()
book(10,20)
book(50,60)
book(10,40)
book(5,15)
book(5,10)
book(25,55)输出: [1,1,2,3,3,3]
说明
前两个可以被预订的事件是不相交的所以说最大的K预订是1预订。
第三个事件[10, 40)和第一个事件相交最大的K预订是2预订。
剩下的事件导致最大的K预订只是3预订。
注意到最后一个事件在本地导致2预订但是答案依然是3预订
因为比如 [10, 20), [10, 40), and [5, 15)依然是三重预订。
样例2输入:
MyCalendarThree()
book(1,2)
book(1,2)
book(2,3)输出: [1,2,2]思路
前置知识线段树
参考代码
class MyCalendarThree {SegmentNode root; //线段树根节点public MyCalendarThree() {root build(0,100000);}public int book(int start, int end) {for (int i start; i end; i) {update(root, i, 1);}return root.max;}static class SegmentNode { //线段树节点定义int start, end, max;SegmentNode left, right;public SegmentNode(int s, int e) {start s;end e;}}//根据开始结束标志创建线段树public static SegmentNode build(int start, int end) {if (start end) return null;if (start end)return new SegmentNode(start, end);SegmentNode root new SegmentNode(start, end);int mid start (end - start) / 2;root.left build(start, mid);root.right build(mid 1, end);return root;}//更新线段树public static void update(SegmentNode root, int index, int val) {if (root.start root.end root.start index) {root.max val;return;}int mid (root.start root.end) / 2;if (index mid index root.start) {update(root.left, index, val);}if (index mid index root.end) {update(root.right, index, val);}root.max Math.max(root.left.max, root.right.max);}
}/*** Your MyCalendarThree object will be instantiated and called as such:* MyCalendarThree obj new MyCalendarThree();* int param_1 obj.book(start,end);*/
