759. 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

   .

思路：合并所有的interval，找到空隙的，可以对所有的interval进行一遍排序（按照interval.start，因为合并要按照start的顺序来才是对的），用优先队列可以进一步简化时间复杂度，省去了整体排序的时间

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
 
class Solution {
    public List<Interval> employeeFreeTime(final List<List<Interval>> avails) {
    	PriorityQueue<int[]> pq = new PriorityQueue<int[]>(50, new Comparator<int[]>(){
			@Override
			public int compare(int[] a1, int[] a2) {
				return avails.get(a1[0]).get(a1[1]).start-avails.get(a2[0]).get(a2[1]).start;
			}
    	});
    	Stack<Interval> st = new Stack<Interval>();
    	
    	for(int i=0; i<avails.size(); i++)
    		pq.add(new int[]{i, 0});
    	
    	while(!pq.isEmpty()) {
    		int[] tt = pq.remove();
    		if(tt[1]+1<avails.get(tt[0]).size()) pq.add(new int[]{tt[0], tt[1]+1});
    		Interval t = avails.get(tt[0]).get(tt[1]);
    		if(st.isEmpty()) {
    			st.add(t);
    		} else {
    			Interval top = st.pop();
    			if(top.end>=t.start) {
    				st.push(new Interval(top.start, Math.max(top.end, t.end)));
    			} else {
    				st.push(top);
    				st.push(t);
    			}
    		}
    	}
    	
    	List<Interval> ret = new ArrayList<Interval>();
    	LinkedList<Interval> t = new LinkedList<Interval>();
    	while(!st.isEmpty())	t.add(0, st.pop());
    	for(int i=0; i<t.size()-1; i++)
    		ret.add(new Interval(t.get(i).end, t.get(i+1).start));
    	return ret;
    }
}