759. Employee Free Time

題目網址： https://leetcode.cn/problems/employee-free-time/

題意：給一員工的 schedule 列表, 表示每個員工的工作時間。

每個員工都有一個非重疊的時段 Intervals 列表, 這些時段皆已由小到大排序。

返回這些員工共同、為正數長度的有限時段列表, 需由小到大排序。

注意：類似 [5, 5] 這樣的時段不能成為答案, 因為長度為 0, 而非正數

Solution 1：

想法：先將所有 intervals flatten 成一維, 再將這些 intervals 由小到大進行排序

• 若 intervals[i - 1].end < intervals[i].start 代表兩個區間沒重疊, 須將 Interval(intervals[i - 1].end, intervals[i].start) 加入到 res 中
• 若 intervals[i - 1].end >= intervals[i].start 代表兩個區間有重疊
• 須更新 end = max(intervals[i - 1].end, intervals[i].end)

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        vector<Interval> all;
        for (const auto& intervals : schedule) {
            all.insert(all.end(), intervals.begin(), intervals.end());
        }

        sort(all.begin(), all.end(), [](const Interval& i1, const Interval& i2){
            return i1.start < i2.start;
        });

        vector<Interval> res;
        int end = all.front().end;

        for (int i = 1; i < all.size(); ++i) {
            if (all[i].start > end) {
                res.emplace_back(Interval(end, all[i].start));
            }
            end = max(end, all[i].end);
        }

        return res;
    }
};

• time：$O(n \cdot log(n))$ ➔ $O(n) + O(n \cdot log(n)) +O(n)$
  • n：所有 interval 的數量
  • $O(n)$：遍歷所有 interval, 並建立 all
  • $O(n \cdot log(n))$：sorting
  • $O(n)$：遍歷 all
• space：$O(n)$ ➔ all

Solution 2：

想法：利用 heap, 概念同 Solution 1, 但是可以少遍歷一次所有的 interval

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
        const auto cmp = [](const Interval& i1, const Interval& i2){
            return i1.start > i2.start;
        };

        // min heap
        priority_queue<Interval, vector<Interval>, decltype(cmp)> q(cmp);
        for (const auto& intervals : schedule) {
            for (const auto& interval : intervals) {
                q.emplace(interval);
            }
        }

        const auto [start, end] = q.top();
        q.pop();

        vector<Interval> res;
        while (!q.empty()) {
            const auto [nextStart, nextEnd] = q.top();
            q.pop();

            if (end < nextStart) {
                res.emplace_back(Interval(end, nextStart));
            }
            end = max(end, nextEnd);
        }

        return res;
    }
};

• time：$O(n \cdot log(n))$ ➔ $O(n)+ O(n \cdot log(n))$
  • n：所有 interval 的數量
  • $O(n)$：遍歷所有 interval, 並建立 min heap, heapify 只需 $O(n)$
  • $O(n \cdot log(n))$：從 heap 中每 pop 一個元素需 $O(log(n))$
• space：$O(n)$ ➔ heap 中元素不超過 n 個