题目描述：
LeetCode 759. Employee Free Time
We are given a list avail of employees, which represents the free 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: avails = [[[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: avails = [[[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, avails[0][0].start = 1, avails[0][0].end = 2, and avails[0][0][0] is not defined.)
Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
Note:
availsandavails[i]are lists with lengths in range[1, 50].0 <= avails[i].start < avails[i].end <= 10^8.
题目大意：
给定数组avails，avails[i]表示第i名员工的所有上班时间区间
求所有员工空闲时间的交集
解题思路：
首先求avails的上班时间区间的补集（空闲区间），并转化为空闲区间链表的数组invList
统计空闲区间总数，记为cnt
循环直到cnt == 0为止：
将invList中各首元素区间取交集，记为joinInv；记首元素的最小值（按照结束时间、起始时间排序）为minInv
若joinInv有效，则将其加入结果列表；
令目标区间targetInv = isValid(joinInv) && joinInv || minInv （当joinInv无效时，取minInv）
遍历invList，假设当前链表为ll：
若首元素的起始时间 >= targetInv的起始时间，则继续循环
否则将首元素与targetInv进行合并，记合并后的区间为ninv，若ninv有效则将其加入ll的头部
Java代码：
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public Interval mergeInterval(Interval ia, Interval ib) {
if (ia == null || ib == null) return null;
Interval ic = new Interval(
Math.max(ia.start, ib.start),
Math.min(ia.end, ib.end));
if (ic.start > ic.end) return null;
return ic;
}
public boolean isValidInterval(Interval inv) {
return inv != null
&& inv.start != Integer.MIN_VALUE
&& inv.end != Integer.MAX_VALUE
&& inv.start < inv.end;
}
public List<Interval> transform(List<Interval> invs) {
List<Interval> ans = new ArrayList<>();
int start = Integer.MIN_VALUE;
for (Interval inv : invs) {
Interval candidate = new Interval(start, inv.start);
if (start < inv.start) {
ans.add(candidate);
}
start = inv.end;
}
ans.add(new Interval(invs.get(invs.size() - 1).end, Integer.MAX_VALUE));
return ans;
}
public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
avails = avails
.stream()
.map(inv->transform(inv))
.collect(Collectors.toList());
Comparator<Interval> cmp = (i1, i2) -> {
if (i1.end == i2.end) return i1.start - i2.start;
return i1.end - i2.end;
};
int cnt = 0;
List<LinkedList<Interval>> invList = new ArrayList<>();
for (int i = 0; i < avails.size(); i++) {
LinkedList<Interval> ll = new LinkedList<>(avails.get(i));
invList.add(ll);
cnt += ll.size();
}
List<Interval> ans = new ArrayList<>();
while (cnt > 0) {
Interval infinite = new Interval(Integer.MIN_VALUE, Integer.MAX_VALUE);
Interval joinInv = invList
.stream()
.map(pq -> pq.isEmpty() ? infinite : pq.peek())
.reduce(infinite, this::mergeInterval);
Interval minInv = invList
.stream()
.map(pq -> pq.isEmpty() ? infinite : pq.peek())
.reduce(infinite, (inv1, inv2) -> {
return cmp.compare(inv1, inv2) < 0 ? inv1 : inv2;
});
if (isValidInterval(joinInv)) {
ans.add(joinInv);
}
Interval targetInv = isValidInterval(joinInv) ? joinInv : minInv;
for (LinkedList<Interval> ll : invList) {
if (ll.isEmpty() || ll.getFirst().start >= targetInv.end) continue;
Interval ninv = new Interval(targetInv.end + 1, ll.removeFirst().end);
if (isValidInterval(ninv)) {
ll.addFirst(ninv);
} else {
cnt -= 1;
}
}
}
return ans;
}
}
本文链接：http://bookshadow.com/weblog/2018/01/07/leetcode-employee-free-time/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
