## Sunday, May 20, 2018

### LeetCode 732 - My Calendar III

https://leetcode.com/problems/my-calendar-iii/description/
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.
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 most 400.
• In calls to MyCalendarThree.book(start, end)start and end are integers in the range [0, 10^9].

• X. Boundary Count
1. 这里用mapvector更加合适， 因为这里的线段的两个端点具有强离散性， 这也是线段树相比于用map不如的地方。
换一种想法： 如果只是保存起始和终点的情况，而完全不管中间经过的点呢？
类似于图， 线段可以看做是一条有向边， 每次从一个点A指向B,相当于A的出度+1， B的入度 + 1。
这种情况下， 找到整个数轴上出度最大的点就是被覆盖次数最多的点。
https://leetcode.com/problems/my-calendar-iii/discuss/109556/JavaC%2B%2B-Clean-Code
This is to find the maximum number of concurrent ongoing event at any time.
We can log the start & end of each event on the timeline, each start add a new ongoing event at that time, each end terminate an ongoing event. Then we can scan the timeline to figure out the maximum number of ongoing event at any time.
The most intuitive data structure for timeline would be array, but the time spot we have could be very sparse, so we can use sorted map to simulate the time line to save space.
    private TreeMap<Integer, Integer> timeline = new TreeMap<>();
public int book(int s, int e) {
timeline.put(s, timeline.getOrDefault(s, 0) + 1); // 1 new event will be starting at [s]
timeline.put(e, timeline.getOrDefault(e, 0) - 1); // 1 new event will be ending at [e];
int ongoing = 0, k = 0;
for (int v : timeline.values())
k = Math.max(k, ongoing += v);
return k;
}

When booking a new event [start, end), count delta[start]++ and delta[end]--. When processing the values of delta in sorted order of their keys, the largest such value is the answer.
In Python, we sort the set each time instead, as there is no analog to TreeMap available.
• Time Complexity: $O(N^2)$, where $N$ is the number of events booked. For each new event, we traverse delta in $O(N)$ time. In Python, this is $O(N^2 \log N)$ owing to the extra sort step.
• Space Complexity: $O(N)$, the size of delta.
TreeMap<Integer, Integer> delta;

public MyCalendarThree() {
delta = new TreeMap();
}

public int book(int start, int end) {
delta.put(start, delta.getOrDefault(start, 0) + 1);
delta.put(end, delta.getOrDefault(end, 0) - 1);

int active = 0, ans = 0;
for (int d: delta.values()) {
active += d;
if (active > ans) ans = active;
}
return ans;
}

https://leetcode.com/problems/my-calendar-iii/discuss/109556/JavaC++-Clean-Code
This is to find the maximum number of concurrent ongoing event at any time.
We can log the start & end of each event on the timeline, each start add a new ongoing event at that time, each end terminate an ongoing event. Then we can scan the timeline to figure out the maximum number of ongoing event at any time.
The most intuitive data structure for timeline would be array, but the time spot we have could be very sparse, so we can use sorted map to simulate the time line to save space.
Java
    private TreeMap<Integer, Integer> timeline = new TreeMap<>();
public int book(int s, int e) {
timeline.put(s, timeline.getOrDefault(s, 0) + 1); // 1 new event will be starting at [s]
timeline.put(e, timeline.getOrDefault(e, 0) - 1); // 1 new event will be ending at [e];
int ongoing = 0, k = 0;
for (int v : timeline.values())
k = Math.max(k, ongoing += v);
return k;
}

X. Binary Search Tree
https://blog.csdn.net/laputafallen/article/details/79676753
https://leetcode.com/problems/my-calendar-iii/discuss/109575/Java-O(n)-BST-Method

class Node{ private int k, v; private Node left, right; public Node(int k, int v) { this.k = k; this.v = v; } } private Node root; private int curt, count; public MyCalendarThree() { } private Node insert(Node node, int k, int v) { if (node == null) { node = new Node(k, v); return node; } else if (node.k == k) { node.v += v; } else if (node.k < k) { node.right = insert(node.right, k, v); } else { node.left = insert(node.left, k, v); } return node; } private void count(Node node) { if (node == null) { return; } count(node.left); curt += node.v; count = Math.max(count, curt); count(node.right); } public int book(int start, int end) { root = insert(root, start, 1); root = insert(root, end, -1); curt = count = 0; count(root); return count; }

X. Segment Tree
http://hehejun.blogspot.com/2018/07/leetcodemy-calendar-iii.html
此外，这也是一道很明显的range query的题目，我们可以用segment tree来解决。具体来说，叶节点存的是当前index对应被覆盖了多少次，非叶节点存的就是这个区间对应的最多的被覆盖的次数。每次插入[s , e]的话就相当于对[s , e]进行range update，区间里的每一个元素加1。区间更新我们用lazy propagation，具体参考上面给出的链接。查询的话直接查根节点储存的信息即可。时间复杂度O(log n)，空间复杂度O(n)
https://blog.csdn.net/Guo15331092/article/details/78883265
线段树放在这道题上其实非常显然， 只需要简单的调用几次线段树的方法就可以得到结果。大致如下：

每次插入一条线段， 对应更新线段树中原先线段上的值。这里，线段的值就是该线段出现的次数。
用一个变量记录最大值。每次在插入线段时维护这个最大值。 插入完之后最大值即为当次结果返回
以上就是线段树的做法。这个做法的缺点如下：
1. 线段树写起来繁琐。 这个写过的自然懂。
2. 线段树的范围太大。 注意到这道题的数据范围对朴素线段树是十分不友好的： 插入次数 < 400, 而插入范围是109109 直接储存直接爆内存应该毫无疑问。 显然要做压缩。
3. 由于是动态查询， 我们不能事先知道线段的起始与终点， 因此压缩比较麻烦。。。

https://leetcode.com/problems/my-calendar-iii/discuss/109568/Java-Solution-O(n-log(len))-beats-100-Segment-Tree
This solution is basically a segment tree solution.
The qurey MyCalendarThree.book(start, end) can be treated as for(i = start; i < end; i++) nums[i] += 1. And the request becomes "find the maximum nums[i]".

To query a range maximum, we process at most two nodes at every level and number of levels is O(logn)1. Thus the overall complexity is O(n log(len)), where len is the length of this segment (ie. 10^9 in this problem).
class MyCalendarThree {
SegmentTree segmentTree;
public MyCalendarThree() {
segmentTree = new SegmentTree(0, 1000000000);
}
public int book(int start, int end) {
return segmentTree.getMax();
}
}

class SegmentTree {
TreeNode root;
public SegmentTree(int left, int right) {
root = new TreeNode(left, right);
}
public void add(int start, int end, int val) {
TreeNode event = new TreeNode(start, end);
}
private void add(TreeNode root, TreeNode event, int val) {
if(root == null) {
return ;
}
/**
* If current node's range lies completely in update query range.
*/
if(root.inside(event)) {
root.booked += val;
root.savedres += val;
}
/**
* If current node's range overlaps with update range, follow the same approach as above simple update.
*/
if(root.intersect(event)) {
// Recur for left and right children.
int mid = (root.start + root.end) / 2;
if(root.left == null) {
root.left = new TreeNode(root.start, mid);
}
if(root.right == null) {
root.right = new TreeNode(mid, root.end);
}
// Update current node using results of left and right calls.
root.savedres = Math.max(root.left.savedres, root.right.savedres) + root.booked;
}
}
public int getMax() {
return root.savedres;
}
/**
* find maximum for nums[i] (start <= i <= end) is not required.
* so i did not implement it.
*/
public int get(int start, int right) {return 0;}
class TreeNode {
int start, end;
TreeNode left = null, right = null;
/**
* How much number is added to this interval(node)
*/
int booked = 0;
/**
* The maximum number in this interval(node).
*/
int savedres = 0;
public TreeNode(int s, int t) {
this.start = s;
this.end = t;
}
public boolean inside(TreeNode b) {
if(b.start <= start && end <= b.end) {
return true;
}
return false;
}
public boolean intersect(TreeNode b) {
if(inside(b) || end <= b.start || b.end <= start) {
return false;
}
return true;
}
}
}

Time Complexity:
To query a range maximum, we process at most two nodes at every level and number of levels is O(logn)1. Thus the overall complexity is O(n log(len)), where len is the length of this segment (ie. 10^9 in this problem

The problem asks you to return an integer K representing the largest integer such that there exists a K-booking in the calendar, i.e., the global max number of overlaps. A K-booking happens when there is some time that is common to K events.
1. In the example when you book (5, 10), the booking itself only causes 2-booking locally, but the global max is still three (made by (10,20), (10,40), (5,15)).
2. (25,55) causes 2-booking with (10,40) or (50,60), while the global max is still three (made by (10,20), (10,40), (5,15)).