## 题目描述：

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:

1. `avails` and `avails[i]` are lists with lengths in range `[1, 50]`.
2. `0 <= avails[i].start < avails[i].end <= 10^8`.

## 解题思路：

```首先求avails的上班时间区间的补集（空闲区间），并转化为空闲区间链表的数组invList

将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) {
}
start = inv.end;
}
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;
for (int i = 0; i < avails.size(); i++) {
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)) {
}
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)) {
} else {
cnt -= 1;
}
}
}
return ans;
}

}
``````

Pingbacks已关闭。