Massive Algorithms: LeetCode 732

LeetCode 732 - My Calendar III

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 most 400.

In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

X. Boundary Count

这里用map比vector更加合适，因为这里的线段的两个端点具有强离散性，这也是线段树相比于用map不如的地方。

换一种想法：如果只是保存起始和终点的情况，而完全不管中间经过的点呢？
类似于图，线段可以看做是一条有向边，每次从一个点A指向B,相当于A的出度+1， B的入度 + 1。
这种情况下，找到整个数轴上出度最大的点就是被覆盖次数最多的点。

这道题的做法十分的棒，是图的出度入度的一个很好的变形，很值得学习

http://leungyukshing.cn/archives/LeetCode%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A%EF%BC%88%E5%85%AD%EF%BC%89--%20732.%20My%20Calendar%20III.html

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.

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://www.cnblogs.com/FannyChung/p/7896415.html

和第一题一样使用BST，没有重叠的区间的节点操作类似第一题，但是对于有重叠区间的节点，要进行分裂，把lser,lsre,slre,sler四种情况总结起来就是中间两个值作为当前节点的起始和终止时间，且次数要增加，两侧分别进行左递归和右递归，次数根据lr还是se再外侧来决定。【selr分别为待插入的start,end，当前节点的left和right】
注意，次数不能简单的为1，对于分裂了lr的情况（如lser和lsre、sler），递归的时候次数可能要指定为当前节点的已有次数，而这个不是固定为1的。所以插入次数也要作为参数进行传递。

    class Node {//节点有起始终止事件，左右子节点，这个时间区间的重叠次数
        int left, right;
        int count;
        Node leftChild, rightChild;

        public Node(int l, int r, int c) {
            left = l;
            right = r;
            count = c;
        }
    }

    int maxK = 1;//只要调用1次book，则最大记录至少为1，所以可以直接初始化为1
    Node root;

    public int book(int start, int end) {
        root = insert(root, start, end, 1);
        return maxK;
    }

    private Node insert(Node root2, int start, int end, int c) {//由于需要修改节点的链接关系，所以需要返回节点
        if (start >= end) {// no need to take action
            return root2;
        }
        if (root2 == null) {
            root2 = new Node(start, end, c);
            return root2;
        }
        int l = root2.left;
        int r = root2.right;
        if (end <= l) {//一定落在当前节点的左侧即左子树上，进行左递归
            root2.leftChild = insert(root2.leftChild, start, end, c);
        } else if (start >= r) {
            root2.rightChild = insert(root2.rightChild, start, end, c);
        } else {
            int[] a = new int[4];//给四个值排序
            if (start <= l) {
                a[0] = start;
                a[1] = l;
            } else {
                a[0] = l;
                a[1] = start;
            }
            if (end <= r) {
                a[2] = end;
                a[3] = r;
            } else {
                a[2] = r;
                a[3] = end;
            }
            root2.left = a[1];//中间的两个值作为当前节点的值
            root2.right = a[2];

            root2.leftChild = insert(root2.leftChild, a[0], a[1], start <= l ? c : root2.count);//左递归，如果start在外侧，则次数为c；如果l在外侧，则次数为当前节点的次数
            root2.rightChild = insert(root2.rightChild, a[2], a[3], end >= r ? c : root2.count);
            root2.count += c;//当前节点的次数要增加，并且根据大小情况选择性的更新maxK
            maxK = Math.max(maxK, root2.count);
        }
        return root2;
    }

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

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) {
        segmentTree.add(start, end, 1);
        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);
     add(root, event, val);
    }
    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);
            }
            add(root.left, event, val);
            if(root.right == null) {
                root.right = new TreeNode(mid, root.end);
            }
            add(root.right, event, val);
            // 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

https://leetcode.com/problems/my-calendar-iii/discuss/109569/Question-explanation-please

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.

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)).
(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)).

X. https://www.acwing.com/solution/LeetCode/content/183/
(端点排序) O(n2)O(n2)
将一个区间拆分为两个端点，并且标记左端点还是右端点。
将这些端点存入一个数组中，记录两个值，一个是这个端点是否是左右端点，一个是这个端点的值。
并且在插入的过程中保持这个数组有序（插入排序）。

接下来维护一个当前区间的最大值
扫描整个数组，碰到左端点值加一，碰到右端点值减一（用纸笔画一下就明白了）。
最后返回最大值。

时间复杂度分析：一共n次插入，每次插入两个元素，并且维持这个数组有序，并且每次都要扫描这个数组。
n次操作，每次操作都需要 O(n)O(n)的复杂度。一共是 O(n2)O(n2)的复杂度
struct node{
int value;
bool isleft;
};

bool cmp(node l,node r){
if (l.value == r.value )
return l.isleft?true:false;
return l.value < r. value;
}
class MyCalendarThree {
public:
vector<node> res;
MyCalendarThree() {
res.resize(0);
}

int book(int start, int end) {
node cur1;
node cur2;

cur1.isleft = true; cur1.value = start;

cur2.isleft = false;cur2.value = end-1;
int sz = res.size();
for (int i = 0;i<res.size();++i){
if (cmp(cur1,res[i])){
res.insert(res.begin()+i,cur1);
break;
}
}
if (res.size() != sz+1)
res.push_back(cur1);
sz = res.size();
for (int i = 0;i<res.size();++i){
if (cmp(cur2,res[i])){
res.insert(res.begin()+i,cur2);
break;
}
}
if (res.size()!= sz+1)
res.push_back(cur2);

int cnt = 0;
int maxres = 0;
for (int i = 0;i<res.size();++i){
if (res[i].isleft) {
cnt++;
maxres = max(maxres,cnt);
}
else
cnt--;
}

return maxres;

}
};

LeetCode 732 - My Calendar III

Labels

Popular Posts