扫描线原型.md

Meeting Room II

解法思路： 统计起点终点在当前时刻的差值

解法1: 扫描线（tree map）

[来源]（https://blog.csdn.net/yurenguowang/article/details/76665171) 将这三个区间在x轴上画出来，并用一条垂直于x轴的线作为扫描线从左至右扫描，会很容易得出答案，即与扫描线焦点的最大值即为所求。但是在程序中我们怎样表示这种思想呢
-对所有点进行标记，区分起始点和终止点
-依次遍历每个点，遇到起始点+1，遇到终止点-1，并更新记录最大值

解法2：存区间终点的最小堆 （priority queue）

-对所有点进行排序
-遍历排序后的区间，priority queue存入区间终点，这样堆顶元素是queue中最小的终点。遍历过程中比较堆顶与当前区间的起点

• initial case： 堆为空，加入当前区间终点，会议室+1
• case1: peek > interval.start, 前一个会议还在占用会议室，需要新的会议室，会议室+1， 加入当前终点作为新的堆顶
• case2: peak <= interval.start, 前一个会议开完，可以继续使用会议室，会议室不变，移除栈顶， 加入当前终点作为新的堆顶

题目解法

    public int minMeetingRooms(int[][] intervals) {
        int ans = 0;        
        Map<Integer, Integer> map = new TreeMap<>();
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            map.put(start, map.getOrDefault(start, 0) + 1);
            map.put(end, map.getOrDefault(end, 0) - 1);
        }
        int count = 0;
        for (int key : map.keySet()) {
            count += map.get(key);
            ans = Math.max(ans, count);
        }
        return ans;
    }

解法2: 用Priority Queue

    public int minMeetingRooms(int[][] intervals) {
        int ans = 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] itv1, int[] itv2) {
                if (itv1[0] == itv2[0]) return itv1[1] - itv2[1];
                return itv1[0] - itv2[0];
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] interval : intervals) {
            if (pq.isEmpty()) {
                pq.offer(interval[1]);
                ++ans;
            } else {
                if (interval[0] >= pq.peek()) {
                    pq.poll();
                } else {
                    ++ans;
                }
                pq.offer(interval[1]);
            }
        }
        return ans;
    }