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.

K-booking 就是说有K个区间彼此重叠。
Interval题关键是要按照开始时间排序，然后再做操作。这道题比较巧妙，利用treemap排序，开始结束时间作为key，开始时间value+1，结束时间value-1。然后遍历树，比如[5, 10] [8, 12]，count是1，2，1，0，所以这两个区间重叠，因为第一个没结束第二个就开始了。

class MyCalendarThree {
    TreeMap<Integer, Integer> timeline;
    public MyCalendarThree() {
        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;
    }
}

57. Insert Interval

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]

分析出三种情况很重要，
1 有交集（交集的子情况也比较多，但两种不相交比较好找），就把待merge数组的start end，再继续去merge
2 interval在待merge数组的前面，把interval加进result
3 interval在待merge数组的后面，把两个数组都加进result，并把merge数组改成null，之后都不管了
最后别忘了如果merge数组不是null的话 将其加入result

// 如果没有排过序
Collections.sort(list, new Comparator<Interval> {
@override
public int compare(Interval i1, Intervali2) {
 return i1.start -i2.start;
}
});

253. Meeting Rooms II

Sweep line

759. Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Sweep Line视频
http://zxi.mytechroad.com/blog/geometry/leetcode-759-employee-free-time/
Keep track of 最大的结束时间，进行merge

    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> list = new ArrayList<>();
        List<Interval> res = new ArrayList<>();
        // flatten intervals to sort
        for (List<Interval> temp : schedule) {
            for (Interval i : temp) {
                list.add(i);
            }
        }
        // sort intervals by star time in increasing order
 
        Comparator<Interval> c = (i1, i2) -> i1.start - i2.start;
        // (a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]
        Collections.sort(list, c);
        // sweep line
        int max_end = list.get(0).end;
        for (int i = 1; i < list.size(); i++) {
            int start = list.get(i).start;
            int end = list.get(i).end;
            if (start < max_end) {
                // has overlap, so merge these two intervals
                
            } else {
                // if no overlap
                if (max_end < start)
                    res.add(new Interval(max_end, start));                
            }
            // then update max_end
            max_end = Math.max(max_end, end);                                    
        }
        return res;
    }