这题相当于找出员工空闲时间方便大家开会一样，跟你每次在outlook上召集会议看大家都什么时候有空是差不多一个道理。
这题标了hard, 其实并不hard。
如果你对interval熟的话，这就是interval的基本操作。
先merge所有 intervals, 然后找出intervals之间的空隙。
如果你对interval不熟的话，那赶紧熟悉起来。
看代码， 真的就是是intervals的基本操作。
其他解法，用sweep line可以做, 也挺简单。
所以如果基础扎实，这道hard应该像切菜一样吧。

class Solution {
    Interval dummyInterval;
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        dummyInterval = new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE);
        List<Interval> mergedIntervals = mergeIntervals(schedule, 0, schedule.size() - 1);
        List<Interval> ans = new ArrayList<>();
        for (int i = 0; i < mergedIntervals.size() - 1; i++) {
            ans.add(new Interval(mergedIntervals.get(i).end, mergedIntervals.get(i + 1).start));
        }
        return ans;
    }
    private List<Interval> mergeIntervals(List<List<Interval>> schedule, int l, int r) {
        if (l > r) return null;
        if (l == r) return schedule.get(l);
        List<Interval> list1 = mergeIntervals(schedule, l, l + (r - l) / 2);
        List<Interval> list2 = mergeIntervals(schedule, l + (r - l) / 2 + 1, r);
        if (list1 == null || list2 == null) return list1 == null ? list2 : list1;
        List<Interval> ans = new ArrayList<>();
        int pt1 = 0, pt2 = 0;
        Interval holder = null;
        while (pt1 < list1.size() || pt2 < list2.size()) {
            Interval itv1 = pt1 < list1.size() ? list1.get(pt1) : dummyInterval;
            Interval itv2 = pt2 < list2.size() ? list2.get(pt2) : dummyInterval; 
            Interval itv = itv1.start < itv2.start ? list1.get(pt1++) : list2.get(pt2++);
            if (holder == null) {
                holder = new Interval(itv.start, itv.end);
            } else {
                if (itv.start > holder.end) {
                    ans.add(new Interval(holder.start, holder.end));
                    holder.start = itv.start;
                    holder.end = itv.end;
                } else {
                    holder.end = Math.max(holder.end, itv.end);
                }
            }
        }
        if (holder != null) ans.add(holder);
        return ans;
    }
}