759. Employee Free Time

sweep-line - use priorityQeueu

T: O(nlogn)

S: O(n)

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
    private static final int START = 1;
    private static final int END = -1;
    
    class TimeInfo {
        int value;
        int type;
        TimeInfo(int value, int type) {
            this.value = value;
            this.type = type;
        }
    }
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        Queue<TimeInfo> pq = new PriorityQueue<>((a, b) -> {
            return a.value == b.value ? a.type - b.type : a.value - b.value;
        });
        for (List<Interval> list : schedule) {
            for (Interval in : list) {
                pq.offer(new TimeInfo(in.start, START)); // start time
                pq.offer(new TimeInfo(in.end, END)); // end time
            }
        }
        
        List<Interval> res = new ArrayList<>();
        int count = 0;
        while (pq.size() > 1) { // need at least 2 data in pq, then we can do the operation
            TimeInfo left = pq.poll();
            TimeInfo right = pq.peek();
            count += left.type;
            // there is a test case [91,94], [94,99] => [94,94], this test can't allow, so check this
            if (left.type == END && right.type == START && count == 0 && left.value != right.value) {
                res.add(new Interval(left.value, right.value));
            }
        }
        return res;
    }
}


/*
[[[1,2],[5,6]],[[1,3]],[[4,10]]]

count = s(1) + e(-1)...

   left right. => if left == e && right == s && count == 0
      |-|
1 1 2 3 4 5 6 10
s s e e s s e  s 
1 2 1 0 1 2 1  2      count  
*/

sweep-line - use treemap

https://leetcode.com/problems/employee-free-time/discuss/175081/Sweep-line-Java-with-Explanations

/*
// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start, int _end) {
        start = _start;
        end = _end;
    }
};
*/

class Solution {
    private static final int START = 1;
    private static final int END = -1;
    
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        
        for (List<Interval> list : schedule) {
            for (Interval in : list) {
                // because use treeMap, so the key will overlap, the START, END should accumulate
                map.put(in.start, map.getOrDefault(in.start, 0) + START); // start time
                map.put(in.end, map.getOrDefault(in.end, 0) + END); // end time
            }
        }
        
        List<Interval> res = new ArrayList<>();
        int count = 0;
        int startFreeTime = -1; // -1 means don't have startFreeTime now
        
        for (int key : map.keySet()) { // need at least 2 data in pq, then we can do the operation
            count += map.get(key);
            if (count == 0 && startFreeTime == -1) { // count == 0, means free time start
                startFreeTime = key;
            // have startFreeTime in pre loop, means we can record endFreeTime now
            } else if (startFreeTime != -1) {
                res.add(new Interval(startFreeTime, key));
                startFreeTime = -1;
            }
        }
        return res;
    }
}


/*
[[[1,2],[5,6]],[[1,3]],[[4,10]]]

count = s(1) + e(-1)...

   if count == 0, save startFreeTime, in next loop, we'll get endFreeTime
  startFreeTime     
      |-|
1 1 2 3 4 5 6 10
s s e e s s e  s 
1 2 1 0 1 2 1  2      count  
*/