Meeting Scheduler

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.  

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68] 

思路：两个array按照start，排序之后，两个指针交替进行打擂台。T( mlogm + nlogn);

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(slots1, (a, b) -> (a[0] - b[0]));
        Arrays.sort(slots2, (a, b) -> (a[0]  -b[0]));
        
        int aIndex = 0; int bIndex = 0;
        while(aIndex < slots1.length && bIndex < slots2.length) {
            int start = Math.max(slots1[aIndex][0], slots2[bIndex][0]);
            int end = Math.min(slots1[aIndex][1], slots2[bIndex][1]);
            if(start < end && end - start >= duration) {
                list.add(start);
                list.add(start + duration);
                break;
            } else {
                // start > end;
                // 注意比较的是尾巴；
                if(slots1[aIndex][1] < slots2[bIndex][1]) {
                    aIndex++;    
                } else {
                    bIndex++;
                }
            }
        }
        return list;
    }
}

通用解法：扫描线，每次count == 2的时候，记录start和end

class Solution {
    class Node {
        public int time;
        public int flag; // 1 means start, -1 means end;
        public Node(int time, int flag) {
            this.time = time;
            this.flag = flag;
        }
    }
    
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        List<Integer> res = new ArrayList<>();
        List<Node> nodes = new ArrayList<>();
        for(int[] slot: slots1) {
            nodes.add(new Node(slot[0], 1));
            nodes.add(new Node(slot[1], -1));
        }
        for(int[] slot: slots2) {
            nodes.add(new Node(slot[0], 1));
            nodes.add(new Node(slot[1], -1));
        }
        Collections.sort(nodes, (a, b) -> {
            if(a.time != b.time) {
                return a.time - b.time;
            } else {
                return a.flag - b.flag;
            }
        });
        
        int start = -1; int end = -1;
        int count = 0;
        for(Node node: nodes) {
            if(node.flag == 1) {
                count++;
                if(count == 2) {
                    start = node.time;
                }
            } else {
                if(count == 2) {
                    if(node.time - start >= duration) {
                        res.add(start);
                        res.add(start + duration);
                        break;
                    } else {
                        start = 0;
                        end = 0;
                    }
                }
                count--;
            }
        }
        return res;
    }
}