Ordered Map (Java) - ShuweiLeung/Thinking GitHub Wiki

1.（855:Hard）（非常非常经典题）Exam Room

• 在编写代码前，需要先理解几个点：

1. Need to measure the distance between seated students: O(n) is trivial, but not as fast. Use PriorityQueue to store the potential candidate as interval, and also calculate the candidate's mid-distance to both side.
2. seat(): pq.poll() to find interval of largest distance. Split and add new intervals back to queue.
3. leave(x): one seat will be in 2 intervals(一个interval的head，一个interval的tail): remove both from pq, and merge to a new interval.
4. Trick（小技巧）: there is no interval when adding for first student, so we need to create boundary/fake seats [-1, N]（可以简化后面边界条件的处理）, which simplifies the edge case a lot. (I spent hours on edge case, and finally saw a smart abstraction using boundary seats).

• 具体思路请看代码，参考链接：PriorityQueue 解决方法

2.（732:Hard）（非常非常经典题）My Calendar III

• 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(加1) at that time, each end terminate(减1) an ongoing event. Then we can scan the timeline to figure out the maximum number of ongoing event at any time.

private TreeMap<Integer, Integer> timeline = new TreeMap<>(); //注意是TreeMap，键值按从小到大排序
public int book(int s, int e) {
    timeline.put(s, timeline.getOrDefault(s, 0) + 1); // 1 new event will be starting at [s],注意以某个时间开始时，value值需要加1，且开始时间对应的value值应该总是正的
    timeline.put(e, timeline.getOrDefault(e, 0) - 1); // 1 new event will be ending at [e]，注意以某个时间结束时，value值需要减1，且结束时间对应的value值应该总是负的
    int ongoing = 0, k = 0;
    for (int v : timeline.values()) //在从前向后扫描的过程中，记录同时进行的booking的最大数目
        k = Math.max(k, ongoing += v);
    return k;
}