http://www.cnblogs.com/grandyang/p/8552586.html
题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。
X. PriorityQueue:
Time Complexity: O(nlogk). k是employee的个数, schedule.size(). n是一共有多少interval.
http://hehejun.blogspot.com/2018/02/leetcodeemployee-free-time.html
此外我们用merge k sorted lists的解法也可以
https://www.cnblogs.com/Dylan-Java-NYC/p/9399311.html
https://blog.csdn.net/zjucor/article/details/79007431
合并所有的interval，找到空隙的，可以对所有的interval进行一遍排序（按照interval.start，因为合并要按照start的顺序来才是对的），用优先队列可以进一步简化时间复杂度，省去了整体排序的时间
X. TreeMap: O(nlogn)
X. Sort Intervals
这道题和之前那道Merge Intervals基本没有太大的区别，那道题是求合并后的区间，这道题求合并后区间中间不相连的区间。那么只要我们合并好了区间，就很容易做了。那么我么首先应该给所有的区间排个序，按照起始位置从小到大来排。因为我们总不可能一会处理前面的，一会处理后面的区间。排好序以后，我们先取出第一个区间赋给t，然后开始遍历所有的区间内所有的区间，如果t的结束位置小于当前遍历到的区间i的起始位置，说明二者没有交集，那么把不相交的部分加入结果res中，然后把当前区间i赋值给t；否则如果区间t和区间i有交集，那么我们更新t的结束位置为二者中的较大值，因为按顺序遍历区间的时候，区间t的结束位置是比较的基准，越大越容易和后面的区间进行合并
X. https://blog.csdn.net/magicbean2/article/details/79569830
X. Videos
花花酱 LeetCode 759. Employee Free Time - 刷题找工作 EP 154
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.
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]
(Even though we are representing
Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)
Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
Note:
scheduleandschedule[i]are lists with lengths in range[1, 50].0 <= schedule[i].start < schedule[i].end <= 10^8.
题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。
X. PriorityQueue:
Time Complexity: O(nlogk). k是employee的个数, schedule.size(). n是一共有多少interval.
http://hehejun.blogspot.com/2018/02/leetcodeemployee-free-time.html
此外我们用merge k sorted lists的解法也可以
https://www.cnblogs.com/Dylan-Java-NYC/p/9399311.html
k条已经排好序的链表. 利用minHeap进行merge.
先把每个表头放在minHeap中. minHeap按照指向的Interval start排序.
poll出来的就是当前最小start的interval. 如果标记的时间比这个interval的start还小就说明出现了断裂也就是空余时间.
把标记时间增大到这个interval的end, 并且把这个interval所在链表的后一位加入minHeap中.
Time Complexity: O(nlogk). k是employee的个数, schedule.size(). n是一共有多少interval.
Space: O(k).
11 public List<Interval> employeeFreeTime(List<List<Interval>> schedule) { 12 List<Interval> res = new ArrayList<Interval>(); 13 PriorityQueue<Node> minHeap = new PriorityQueue<Node>((a,b) -> 14 schedule.get(a.employee).get(a.index).start - schedule.get(b.employee).get(b.index).start); 15 16 int start = Integer.MAX_VALUE; 17 for(int i = 0; i<schedule.size(); i++){ 18 minHeap.add(new Node(i, 0)); 19 start = Math.min(start, schedule.get(i).get(0).start); 20 } 21 22 while(!minHeap.isEmpty()){ 23 Node cur = minHeap.poll(); 24 if(start < schedule.get(cur.employee).get(cur.index).start){ 25 res.add(new Interval(start, schedule.get(cur.employee).get(cur.index).start)); 26 } 27 28 start = Math.max(start, schedule.get(cur.employee).get(cur.index).end); 29 cur.index++; 30 if(cur.index < schedule.get(cur.employee).size()){ 31 minHeap.add(cur); 32 } 33 } 34 35 return res; 36 } 39 class Node{ 40 int employee; 41 int index; 42 public Node(int employee, int index){ 43 this.employee = employee; 44 this.index = index; 45 } 46 }
合并所有的interval，找到空隙的，可以对所有的interval进行一遍排序（按照interval.start，因为合并要按照start的顺序来才是对的），用优先队列可以进一步简化时间复杂度，省去了整体排序的时间
public List<Interval> employeeFreeTime(final List<List<Interval>> avails) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(50, new Comparator<int[]>() {
@Override
public int compare(int[] a1, int[] a2) {
return avails.get(a1[0]).get(a1[1]).start - avails.get(a2[0]).get(a2[1]).start;
}
});
Stack<Interval> st = new Stack<Interval>();
for (int i = 0; i < avails.size(); i++)
pq.add(new int[] { i, 0 });
while (!pq.isEmpty()) {
int[] tt = pq.remove();
if (tt[1] + 1 < avails.get(tt[0]).size())
pq.add(new int[] { tt[0], tt[1] + 1 });
Interval t = avails.get(tt[0]).get(tt[1]);
if (st.isEmpty()) {
st.add(t);
} else {
Interval top = st.pop();
if (top.end >= t.start) {
st.push(new Interval(top.start, Math.max(top.end, t.end)));
} else {
st.push(top);
st.push(t);
}
}
}
List<Interval> ret = new ArrayList<Interval>();
LinkedList<Interval> t = new LinkedList<Interval>();
while (!st.isEmpty())
t.add(0, st.pop());
for (int i = 0; i < t.size() - 1; i++)
ret.add(new Interval(t.get(i).end, t.get(i + 1).start));
return ret;
}
X. TreeMap: O(nlogn)
我们再来看一种解法，这种解法挺巧妙的，我们使用TreeMap建立一个位置和其出现次数之间的映射，对于起始位置，进行正累加，对于结束位置，进行负累加。由于TreeMap具有自动排序的功能，所以我们进行遍历的时候，就是从小到大进行遍历的。定义一个变量cnt，初始化为0，我们对于每个遍历到的数，都加上其在TreeMap中的映射值，即该数字出现的次数，起始位置的话就会加正数，结束位置就是加负数。开始的时候，第一个数字一定是个起始位置，那么cnt就是正数，那么接下来cnt就有可能加上正数，或者减去一个负数，我们想，如果第一个区间和第二个区间没有交集的话，那么接下来遇到的数字就是第一个区间的结束位置，所以会减去1，这样此时cnt就为0了，这说明一定会有中间区域存在，所以我们首先把第一个区间当前起始位置，结束位置暂时放上0，组成一个区间放到结果res中，这样我们在遍历到下一个区间的时候更新结果res中最后一个区间的结束位置。语言描述难免太干巴巴的，我们拿题目中的例1来说明，建立好的TreeMap如下所示：
1 -> 2
2 -> -1
3 -> -1
4 -> 1
5 -> 1
6 -> -1
10 -> -1
2 -> -1
3 -> -1
4 -> 1
5 -> 1
6 -> -1
10 -> -1
那么开始遍历这所有的映射对，cnt首先为2，然后往后遍历下一个映射对2 -> -1，此时cnt为1了，不进行其他操作，再往下遍历，下一个映射对3 -> -1，此时cnt为0了，说明后面将会出现断层了，我们将(3, 0)先存入结果res中。然后遍历到4 -> 1时，cnt为1，此时将结果res中的(3, 0)更新为 (3, 4)。然后到5 -> 1，此时cnt为2，不进行其他操作，然后到6 -> -1，此时cnt为1，不进行其他操作，然后到10 -> -1，此时cnt为0，将(10, 0)加入结果res中。由于后面再没有任何区间了，所以res最后一个区间不会再被更新了，我们应该将其移出结果res，因为题目中限定了区间不能为无穷，参见代码如下：
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) { vector<Interval> res; map<int, int> m; int cnt = 0; for (auto employee : schedule) { for (Interval i : employee) { ++m[i.start]; --m[i.end]; } } for (auto a : m) { cnt += a.second; if (!cnt) res.push_back(Interval(a.first, 0)); if (cnt && !res.empty() && !res.back().end) res.back().end = a.first; } if (!res.empty()) res.pop_back(); return res; }
X. Sort Intervals
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
vector<Interval> all;
for (const auto intervals : schedule)
all.insert(all.end(), intervals.begin(), intervals.end());
std::sort(all.begin(), all.end(),
[](const Interval& a, const Interval& b){
return a.start < b.start;
});
vector<Interval> ans;
int end = all.front().end;
for (const Interval& busy : all) {
if (busy.start > end)
ans.emplace_back(end, busy.start);
end = max(end, busy.end);
}
return ans;
}
这道题和之前那道Merge Intervals基本没有太大的区别，那道题是求合并后的区间，这道题求合并后区间中间不相连的区间。那么只要我们合并好了区间，就很容易做了。那么我么首先应该给所有的区间排个序，按照起始位置从小到大来排。因为我们总不可能一会处理前面的，一会处理后面的区间。排好序以后，我们先取出第一个区间赋给t，然后开始遍历所有的区间内所有的区间，如果t的结束位置小于当前遍历到的区间i的起始位置，说明二者没有交集，那么把不相交的部分加入结果res中，然后把当前区间i赋值给t；否则如果区间t和区间i有交集，那么我们更新t的结束位置为二者中的较大值，因为按顺序遍历区间的时候，区间t的结束位置是比较的基准，越大越容易和后面的区间进行合并
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) { vector<Interval> res, v; for (auto a : schedule) { v.insert(v.end(), a.begin(), a.end()); } sort(v.begin(), v.end(), [](Interval &a, Interval &b) {return a.start < b.start;}); Interval t = v[0]; for (Interval i : v) { if (t.end < i.start) { res.push_back(Interval(t.end, i.start)); t = i; } else { t = (t.end < i.end) ? i : t; } } return res; }
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<>();
List<Interval> times = new ArrayList<>();
for (List<Interval> list: schedule) {
times.addAll(list);
}
Collections.sort(times, ((i1, i2)->i1.start-i2.start));
Interval pre = times.get(0);
for (int i = 1; i < times.size(); i++) {
Interval cur = times.get(i);
if (cur.start <= pre.end) {
pre.end = cur.end > pre.end ? cur.end : pre.end;
} else {
res.add(new Interval(pre.end, cur.start));
pre = cur;
}
}
return res;
}
我们首先将所有员工的工作时段进行合并。然后从合并后的intervals中找出有限的空余时段即可。整个算法的时间复杂度是O(nlogn)，空间复杂度是O(n)，其中n是所有员工的工作时段的总数。
vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
vector<Interval> intervals, result, ans;
for (int i = 0; i < schedule.size(); ++i) {
for (int j = 0; j < schedule[i].size(); ++j) {
intervals.push_back(schedule[i][j]);
}
}
sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
return a.start < b.start || (a.start == b.start && a.end < b.end); });
result.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i].start <= result.back().end) {
result.back().end = max(result.back().end, intervals[i].end);
}
else {
result.push_back(intervals[i]);
}
}
for (int i = 0; i + 1 < result.size(); ++i) {
if (result[i].end < result[i + 1].start) {
ans.push_back(Interval(result[i].end, result[i + 1].start));
}
}
return ans;
}
X. Videos
