]], [[3,5], [7,9]]] Output: [5,7] Explanation: All employees are free between [5,7].

Solution

Method 1

Intuition

We want to find gaps between all employees' working intervals. Since each employee's intervals are sorted, we can efficiently merge all intervals and look for gaps. Using a min-heap allows us to always process the earliest interval next, making it easy to find free time between intervals.

Approach

Insert the first interval of each employee into a min-heap (ordered by start time).
Track the latest end time seen so far.
Pop the smallest start-time interval from the heap, and if its start is after the latest end, record the gap as free time.
Update the latest end time.
If the employee has more intervals, push the next one into the heap.
Repeat until all intervals are processed.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {\n        using T = tuple<int, int, int, int>; // start, end, emp, idx\n        priority_queue<T, vector<T>, greater<T>> pq;\n        for (int i = 0; i < schedule.size(); ++i)\n            pq.emplace(schedule[i][0][0], schedule[i][0][1], i, 0);\n        int prevEnd = get<1>(pq.top());\n        vector<vector<int>> res;\n        while (!pq.empty()) {\n            auto [start, end, emp, idx] = pq.top(); pq.pop();\n            if (start > prevEnd)\n                res.push_back({prevEnd, start});\n            prevEnd = max(prevEnd, end);\n            if (idx + 1 < schedule[emp].size())\n                pq.emplace(schedule[emp][idx+1][0], schedule[emp][idx+1][1], emp, idx+1);\n        }\n        return res;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code>&#

Related Tags