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;
}
