1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package airbnb;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;


/**
 * 每个subarray都已经sort好
举例：
[
  [[1, 3], [6, 7]],
  [[2, 4]],
  [[2, 3], [9, 12]].
]
返回
[[4, 6], [7, 9]]
N个员工，每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals
解法：这题最简单的方法就是把所有区间都拆成两个点，然后排序，然后扫描，每次碰到一个点如果
是左端点就把busy_employees加1，否则减1，等到每次busy_employees为0时就是一个新的区间。
这样复杂度O(MlogM)，M是总共区间数。但是我当时也不知道是脑抽了还是脑子太好用了，弄了个堆的，
堆里N个元素，存每个员工的下一个端点，如果堆顶是某个员工的左端点就busy_employees加1，否则减1。
这样好处是时间复杂度低了一点点，坏处是给面试官讲了半天而且代码不是太好写……不建议这么做.
 * @author yihuifu
 *
 */
public class MeetingIntervals {

	public static void main(String[] args) {
		MeetingIntervals meetingIntervals = new MeetingIntervals();
		List<List<Interval>> intervals = new LinkedList<>();
		for (int i = 0; i < 3; i++) {
			intervals.add(new LinkedList<>());
			switch (i) {
				case 0: 
					intervals.get(i).add(meetingIntervals.new Interval(1,3));
					intervals.get(i).add(meetingIntervals.new Interval(6,7));
					break;
				case 1:
					intervals.get(i).add(meetingIntervals.new Interval(2,8));
					break;
				case 2:
					intervals.get(i).add(meetingIntervals.new Interval(2,3));
					intervals.get(i).add(meetingIntervals.new Interval(9,12));
					break;
			}
		}
		List<Interval> freeIntervals = meetingIntervals.findFreeIntervals(intervals);
		for (Interval interval : freeIntervals) {
			System.out.println(interval.toString());
		}
	}
	
	public List<Interval> findFreeIntervals(List<List<Interval>> intervals) {
		List<Interval> result = new LinkedList<>();
		if (intervals == null || intervals.size() == 0) {
			return result;
		}
		LinkedList<Interval> all = new LinkedList<>();
		for (int i = 0; i < intervals.size(); i++) {
			for (int j = 0; j < intervals.get(i).size(); j++) {
				all.add(intervals.get(i).get(j));
			}
		}
		Collections.sort(all, (a,b) -> (a.startTime - b.startTime));
		PriorityQueue<Interval> pq = new PriorityQueue<>((a,b) -> a.endTime - b.endTime);
		pq.offer(all.get(0));
		for (int i = 1; i < all.size(); i++) {
			Interval prev = pq.poll();
			Interval cur = all.get(i);
			if (cur.startTime <= prev.endTime) {
				prev.endTime = Math.max(prev.endTime, cur.endTime);
			} else {
				pq.offer(cur);
			}
			pq.offer(prev);
		}
		Interval prev = pq.poll();
		while (!pq.isEmpty()) {
			Interval cur = pq.poll();
			result.add(new Interval(prev.endTime, cur.startTime));
			prev = cur;
		}
		return result;
	}
	
	public class Interval {
		int startTime;
		int endTime;
		
		public Interval(int start, int end) {
			startTime = start;
			endTime = end;
		}
		
		@Override
		public String toString() {
			return "" + startTime + " " + endTime;
		}
	}

}