# 0759. Employee Free Time
###### tags: `Leetcode` `Hard` `Line Sweep`
Link: https://leetcode.com/problems/employee-free-time/
## 思路 $O(NlogN)$ $O(N)$
先用差分法+prefixSum 找到每个时间都有几个人occupied，找到occupied的人数=0的interval
## Code

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        TreeMap<Integer, Integer> line = new TreeMap<>();
        for(List<Interval> list:schedule){
            for(Interval i:list){
                line.put(i.start, line.getOrDefault(i.start, 0)+1);
                line.put(i.end, line.getOrDefault(i.end,0)-1);
            }
        }
        
        int score = 0, prev = -1;
        List<Interval> ans = new ArrayList<>();
        for(int time:line.keySet()){
            score += line.get(time);
            if(score==0 && prev==-1) prev=time;
            else if(score!=0 && prev!=-1){
                ans.add(new Interval(prev, time));
                prev = -1;
            }
        }
        
        return ans;
    }
}