759. 员工空闲时间
给定员工的 schedule 列表，表示每个员工的工作时间。
每个员工都有一个非重叠的时间段 Intervals 列表，这些时间段已经排好序。
返回表示 所有 员工的 共同，正数长度的空闲时间 的有限时间段的列表，同样需要排好序。
示例 1：
输入：schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] 输出：[[3,4]] 解释： 共有 3 个员工，并且所有共同的 空间时间段是 [-inf, 1], [3, 4], [10, inf]。 我们去除所有包含 inf 的时间段，因为它们不是有限的时间段。
示例 2：
输入：schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] 输出：[[5,6],[7,9]]
（尽管我们用 [x, y] 的形式表示 Intervals ，内部的对象是 Intervals 而不是列表或数组。例如，schedule[0][0].start = 1, schedule[0][0].end = 2，并且 schedule[0][0][0] 是未定义的）
而且，答案中不包含 [5, 5] ，因为长度为 0。
注：
schedule 和 schedule[i] 为长度范围在 [1, 50]的列表。0 <= schedule[i].start < schedule[i].end <= 10^8。注：输入类型于 2019 年 4 月 15 日 改变。请重置为默认代码的定义以获取新方法。
原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-17 20:24:56
/**
* Definition for an Interval.
* type Interval struct {
* Start int
* End int
* }
*/
func employeeFreeTime(schedule [][]*Interval) (ans []*Interval) {
a := []int{}
for _, s := range schedule {
for _, p := range s {
a = append(a, p.Start<<1, p.End<<1|1) // 最低位表示区间左右
}
}
sort.Ints(a)
s := 0
for i, v := range a {
s += 1 - v&1<<1 // 根据左右 +1 或 -1
if s == 0 && i+1 < len(a) {
ans = append(ans, &Interval{v >> 1, a[i+1] >> 1})
}
}
return
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 10.8 MB, 提交时间: 2023-10-17 20:24:23
/*
// Definition for an Interval.
class Interval {
public:
int start;
int end;
Interval() {}
Interval(int _start, int _end) {
start = _start;
end = _end;
}
};
*/
class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
priority_queue<Interval,vector<Interval>,function<bool(const Interval&, const Interval&)>> pq{[&](const Interval& i1, const Interval& i2) {
if(i1.start!=i2.start)
return i1.start>i2.start;
else
return i1.end>i2.end;
}};
for(auto &intervals:schedule) {
for(auto &interval:intervals)
pq.push(interval);
}
vector<Interval> ret;
int l=-1;
int r=-1;
while(!pq.empty()) {
Interval t=pq.top();pq.pop();
r=max(r,t.start);
if(l!=-1&&l<r)
ret.emplace_back(Interval(l,r));
l=max(l,t.end);
}
return ret;
}
};
java 解法, 执行用时: 14 ms, 内存消耗: 43.6 MB, 提交时间: 2023-10-17 20:23:31
/*
// Definition for an Interval.
class Interval {
public int start;
public int end;
public Interval() {}
public Interval(int _start, int _end) {
start = _start;
end = _end;
}
};
*/
class Solution {
public List<Interval> employeeFreeTime1(List<List<Interval>> avails) {
int OPEN = 0, CLOSE = 1;
List<int[]> events = new ArrayList();
for (List<Interval> employee: avails)
for (Interval iv: employee) {
events.add(new int[]{iv.start, OPEN});
events.add(new int[]{iv.end, CLOSE});
}
Collections.sort(events, (a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);
List<Interval> ans = new ArrayList();
int prev = -1, bal = 0;
for (int[] event: events) {
// event[0] = time, event[1] = command
if (bal == 0 && prev >= 0)
ans.add(new Interval(prev, event[0]));
bal += event[1] == OPEN ? 1 : -1;
prev = event[0];
}
return ans;
}
// 优先队列
public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
List<Interval> ans = new ArrayList();
PriorityQueue<Job> pq = new PriorityQueue<Job>((a, b) ->
avails.get(a.eid).get(a.index).start -
avails.get(b.eid).get(b.index).start);
int ei = 0, anchor = Integer.MAX_VALUE;
for (List<Interval> employee: avails) {
pq.offer(new Job(ei++, 0));
anchor = Math.min(anchor, employee.get(0).start);
}
while (!pq.isEmpty()) {
Job job = pq.poll();
Interval iv = avails.get(job.eid).get(job.index);
if (anchor < iv.start)
ans.add(new Interval(anchor, iv.start));
anchor = Math.max(anchor, iv.end);
if (++job.index < avails.get(job.eid).size())
pq.offer(job);
}
return ans;
}
}
class Job {
int eid, index;
Job(int e, int i) {
eid = e;
index = i;
}
}
python3 解法, 执行用时: 88 ms, 内存消耗: 18 MB, 提交时间: 2023-10-17 20:22:35
"""
# Definition for an Interval.
class Interval:
def __init__(self, start: int = None, end: int = None):
self.start = start
self.end = end
"""
class Solution:
# 扫描线
def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
OPEN, CLOSE = 0, 1
events = []
for emp in schedule:
for iv in emp:
events.append((iv.start, OPEN))
events.append((iv.end, CLOSE))
events.sort()
ans = []
prev = None
bal = 0
for t, cmd in events:
if bal == 0 and prev is not None:
ans.append(Interval(prev, t))
bal += 1 if cmd is OPEN else -1
prev = t
return ans
# 优先队列
def employeeFreeTime2(self, schedule: '[[Interval]]') -> '[Interval]':
ans = []
pq = [(emp[0].start, ei, 0) for ei, emp in enumerate(avails)]
heapq.heapify(pq)
anchor = min(iv.start for emp in avails for iv in emp)
while pq:
t, e_id, e_jx = heapq.heappop(pq)
if anchor < t:
ans.append(Interval(anchor, t))
anchor = max(anchor, avails[e_id][e_jx].end)
if e_jx + 1 < len(avails[e_id]):
heapq.heappush(pq, (avails[e_id][e_jx+1].start, e_id, e_jx+1))
return ans