LeetCode 759. Employee Free Time
原题链接
困难
作者:
JasonSun
,
2020-01-17 04:12:00
,
所有人可见
,
阅读 710
Algorithm
- We first merge the intervals and sort the merged intervals by the starting point and then count the leftout middle pieces.
- The merge procedure is quite standard, if you can merge them by hand you can merge them using recursion.
Code
class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
const auto pooled_schedules = [&](vector<Interval> self = {}) {
for (const auto & s : schedule)
std::copy(begin(s), end(s), std::back_inserter(self));
std::sort(begin(self), end(self), [](const auto & x, const auto & y) {
return x.start < y.start;
});
return self;
}();
const auto merged_intervals = [&](vector<Interval> self = {}) {
function<void(int)> go = [&] (int pos) {
if (pos == size(pooled_schedules))
return;
else if (pos == 0) {
self.emplace_back(pooled_schedules[pos]);
go(pos + 1);
}
else {
const auto [last_start, last_end] = self.back();
const auto [cur_start, cur_end] = pooled_schedules[pos];
if (cur_start > last_end)
self.emplace_back(pooled_schedules[pos]);
else
self.back().end = std::max(cur_end, last_end);
go(pos + 1);
}
};
return (go(0), self);
}();
const auto solution = [&]() -> vector<Interval> {
if (size(merged_intervals) == 0)
return {};
else
return [&](vector<Interval> self = {}) {
for (int i = 1; i < size(merged_intervals); ++i) {
const auto [start, end] = tuple(merged_intervals[i - 1].end, merged_intervals[i].start);
self.emplace_back(Interval{start, end});
}
return self;
}();
}();
return solution;
}
};