Facebook Phone Interview 2: 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 time for 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.

 

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

 

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

Notes: 

One straightforward way is to merge all the internals by removing the overlapping, then find the "the empty" intervals.  By using priority_queue to pop up the next available interval, we can solve this problem in O(m*n*log(m)), where m is the size of schedule and n is the size of schedule[i].

Another way is to use the scan-line algorithm: sort all the beginning and ending time, then scan them from the left to right. Use a count to represent how many people are working in that time interval.

Since we have m*n intervals, thus we will have 2*m*n elements (both starting and ending times), then the time complexity is O(2*m*n*log(2*m*n)). But it is easy to code.

class Solution {
public:
    vector<vector<int>> findCommonFreetime(vector<vector<vector<int>>>& mt) {
    	if (!mt.size()) return 0;
        vector<pair<int, int>> data;
        for (auto &a : mt) {
	    for(auto &b : a) {
		data.push_back({b[0], 1});
                data.push_back({b[1], -1});
	    }
        }
	sort(data.begin(), data.end());
	int ct = 0, left = -1;
 	for (int i=0; i<data.size(); ++i) {
	    auto t = data[i];
	    if(t.second == 1) {
                ++ct;
                if (ct == 1 && left != -1 && left < t.first) {
                    vector<int> temp;
                    temp.push_back(left);
                    temp.push_back(t.first);
                    res.push_back(temp);
                    left = -1;
		}
	    else --ct;
            if (ct==0) left = t.first; 
	}
	return res;
    }
}