Leetcode : Employee Free Time

We are given a list schedule of employees, which represents the working 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 timefor all employees, also in sorted order.

Example 1:

Input: schedule = [[[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. 

Analysis:

The thoughts of how to tackle this problem is very straight forward, however, choosing which kind of data structure to present and get the answer efficiently and also easy to understand is the difficult part. 

List all the intervals on a timeline, then it will look like this 

b1(b1)      e2      e3     b4     b5     e6                          e10

________________________________________________________________________

So we can see the answer that we need is [e3, b4], and we can easily tell the condition is when the time interval meets situation curEnd < curBegin. 

In the very first place, I thought of using PriorityQueue. Using two priority queues, then push startTime and endTime separately, then compare each pq.top() value. However, this meets a lot of corner cases, especially hard to decide what is the loop end condition.

Then I found out, why not just pair the start and end time up, by increasing order? 

For example: 

Begin: 1, 2, 2, 6

End:    3, 4, 5, 7

Because their sizes are the same, the condition for free time slot is simple, end[i] < begin[i+1]. 

Time complexity: O(nlogn) for sorting. Space complex: O(n). 

class Solution {
public:
    vector<vector<int>> employeeFreeTime(vector<vector<vector<int>>>& schedule) {
        vector<vector<int>> res;
        vector<int> tmp;
        vector<int> begin, end;
        
        for (int i = 0; i<schedule.size(); i++)
        {
            for (int j = 0; j<schedule[i].size(); j++)
            {
                begin.push_back(schedule[i][j][0]);
                end.push_back(schedule[i][j][1]);
            }
        }
        
       sort(begin.begin(), begin.end());
       sort(end.begin(), end.end());
       for (int i = 0; i<begin.size(); i++)
       {
           if (i<begin.size()-1 && end[i] < begin[i+1])
            {
                tmp.push_back(end[i]);
                tmp.push_back(begin[i+1]);
                res.push_back(tmp);
                tmp.clear();
            }
       }
            
        return res;
    }
};