7/5, Interval 类，扫描线

7/5, Interval 类，扫描线

Interval 类问题中最常用的技巧，就是自定义 IntervalComparator，把输入按照 startTime 升序排序。

对于任意两个区间A与B，如果

• A.end > B.start 并且

• A.start < B.end

• 则 A 与 B 重叠。

按 start 排序后，数组有了单调性，上面的判断条件就简化成了 A.end > B.start 则一定重叠.

排序后的 Interval 扫描过程中，为了保证正确性，要格外小心多个 Interval 在同一 x 时，处理的先后顺序，比如 skyline problem.

熟悉下 TreeMap 的常用 API.

• get()

  • put()

  • containsKey()

  • size()

  • values() : 返回 Collection<> of V

  • lowerKey(K key) ： 返回最大的小于参数的Key，没有则 null

  • higherKey(K key)：返回最小的大于参数的Key, 没有则 null

  • firstKey() : 返回最小 key

  • lastKey() : 返回最大 key

Meeting Rooms

Trivial Problem.

public class Solution {
    private class IntervalComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }

    public boolean canAttendMeetings(Interval[] intervals) {
        if(intervals == null || intervals.length <= 1) return true;

        Arrays.sort(intervals, new IntervalComparator());

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < intervals[i - 1].end) return false;

        }

        return true;
    }
}

Meeting Rooms II

fb 面经高频题，follow up 是返回那个 overlap 最多的区间。

另一个 fb onsite 面经题里，首先给 n 个一维 interval，返回任意重合最多的点；然后给 n 个二维 rectangle，返回任意重复最多的点。

扫描线算法。需要注意的是如果有两个 interval 首尾相接，要把结束的那个排在 array 的前面，先把房间腾出来；否则的话会认为收尾相接的两个 meeting 需要占 2 个房间，这是错误的。

public class Solution {
    private class Point{
        int time;
        boolean isStart;
        public Point(int time, boolean isStart){
            this.time = time;
            this.isStart = isStart;
        }
    }

    private class PointComparator implements Comparator<Point>{
        public int compare(Point a, Point b){
            if(a.time == b.time) return a.isStart ? 1 : -1 ;
            else return a.time - b.time;
        }
    }

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;

        Point[] arr = new Point[intervals.length * 2];

        for(int i = 0; i < intervals.length; i++){
            arr[i * 2] = new Point(intervals[i].start, true);
            arr[i * 2 + 1] = new Point(intervals[i].end, false);
        }

        Arrays.sort(arr, new PointComparator());

        int maxOverLap = 0;
        int curCount = 0;
        for(Point pt : arr){
            if(pt.isStart) curCount ++;
            else curCount --;
            maxOverLap = Math.max(maxOverLap, curCount);
        }

        return maxOverLap;
    }
}

(FB) follow-up: 如何返回重叠最多的那个区间？

• 当前 maxOverlap 创造新高的时候，存下 start 的时间戳，因为这是所有重合区间中 start 时间最晚的一个；

• 继续扫描，看到新的 end 的时候，存下这个 end 的时间戳，因为它是重合区间里 end 时间最早的一个；

• 二者之间，就是具体的 max overlap 区间。

针对这题还有另外一种写法，用 heap / PriorityQueue，相比之下代码量要小一点，不过不像扫描线算法那样清晰易于理解，而且容易进行修改适应各种 follow-up 情况。

public class Solution {
    private class IntervalComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;

        Arrays.sort(intervals, new IntervalComparator());

        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        heap.offer(intervals[0].end);
        int maxOverLap = 1;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < heap.peek()){
                maxOverLap ++;
            } else {
                heap.poll();
            }
            heap.offer(intervals[i].end);
        }

        return maxOverLap;
    }
}

Merge Intervals

这题需要注意的 corner case 有两个：

• 按 startTime 排序后， merge 的新 interval 可能是完全包含于前一个 interval 的，如 【1,4】，【2,3】. 所以当发现 overlap 时，新的 End 要以两个 end 的最大值为准。

• 记得循环尾部做一个收尾，把最后 merge 完的结果生成新的 interval 也加到 list 中。

public class Solution {
    private class IntervalComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }

    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> list = new ArrayList<Interval>();
        if(intervals == null || intervals.size() == 0) return list;

        Collections.sort(intervals, new IntervalComparator());

        int curStart = intervals.get(0).start;
        int curEnd = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); i++){
            Interval cur = intervals.get(i);
            if(cur.start > curEnd){
                list.add(new Interval(curStart, curEnd));
                curStart = cur.start;
                curEnd = cur.end;
            } else {
                curEnd = Math.max(curEnd, cur.end);
            }
        }

        list.add(new Interval(curStart, curEnd));

        return list;
    }
}

Insert Interval

顺着上一题的思路，一个最简单直接的写法就是。。直接把新的 interval 插进去，然后再跑一遍 merge interval 的代码。

考虑到一些极端情况，比如 newInterval 合并了原始 list 中绝大多数 intervals, 在原 list 上进行操作的话需要的比较与删减也会很多，所以从算法复杂度上讲，这种写法至少可以 AC，但不是最优。

时间复杂度 O(n log n ) + O(n)

public class Solution {
    private class IntervalComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        intervals.add(newInterval);

        Collections.sort(intervals, new IntervalComparator());

        List<Interval> list = new ArrayList<Interval>();

        int curStart = intervals.get(0).start;
        int curEnd = intervals.get(0).end;

        for(int i = 1; i < intervals.size(); i++){
            Interval cur = intervals.get(i);
            if(cur.start > curEnd){
                list.add(new Interval(curStart, curEnd));
                curStart = cur.start;
                curEnd = cur.end;
            } else {
                curEnd = Math.max(curEnd, cur.end);
            }
        }
        list.add(new Interval(curStart, curEnd));

        return list;
    }
}

如果要进行进一步优化，要利用原题中 set of "non-overlapping" intervals 的条件，所以 newInterval 有可能会与任何 interval 或 N 个 interval 的集合，在左右两边 merge [0, N] 个 interval, 从完全 disjoint 到完全合并。

时间复杂度 O(n)，one-pass.

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> list = new ArrayList<>();

        int ptr = 0;
        int n = intervals.size();

        while(ptr < n && intervals.get(ptr).end < newInterval.start) list.add(intervals.get(ptr++));
        while(ptr < n && intervals.get(ptr).start <= newInterval.end){
            newInterval.start = Math.min(newInterval.start, intervals.get(ptr).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(ptr).end);
            ptr ++;
        }
        list.add(newInterval);
        while(ptr < n) list.add(intervals.get(ptr++));

        return list;
    }

在此基础上还可以进一步优化，不用额外空间，on-the-fly 解决战斗。

这种做法可以不花费任何额外空间，但是时间复杂度会更高，因为 List.remove() 是一个 O(n) 操作，add(index, val) 也是 O(n) 的。

    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int ptr = 0;

        while(ptr < intervals.size() && intervals.get(ptr).end < newInterval.start) ptr++;
        while(ptr < intervals.size() && intervals.get(ptr).start <= newInterval.end){
            newInterval.start = Math.min(newInterval.start, intervals.get(ptr).start);
            newInterval.end = Math.max(newInterval.end, intervals.get(ptr).end);
            intervals.remove(ptr);
        }
        intervals.add(ptr, newInterval);

        return intervals;
    }

Summary Ranges

一个比较简单的区间融合问题。

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        if(nums == null || nums.length == 0) return list;

        Integer start = null; 
        Integer end = null;

        for(int i = 0; i < nums.length; i++){
            if(start == null){
                start = nums[i];
                end = nums[i];
            } else if(nums[i] == end + 1){
                end ++;
            } else {
                if(!start.equals(end))list.add("" + start + "->" + end);
                else list.add("" + start);

                start = nums[i];
                end = nums[i];
            }
        }
        if(!start.equals(end))list.add("" + start + "->" + end);
        else list.add("" + start);

        return list;
    }
}

Missing Ranges

第一种不太经济的写法是，建一个 boolean[upper - lower + 1] ，扫一遍数组记录下每个数是否出现过，然后根据 boolean[] 的 flag 进行融合。 这种写法首先需要 O(upper - lower) 的 extra space，而且最重要的是，没有利用到原数组 int[] 已经是排序了的性质，因此速度上不给力，而且在 upper = 100000000, lower = -10000000 这种极端情况下，空间占用非常大。

改进后的代码实现过程中，最开始没有考虑全 test case，虽然AC 了但是代码不够 clean. 下面参考论坛里的解法就简明了很多。

如果实现代码的时候发现要写很多 if else 处理特殊情况，最好的选择还是暂停一下，多把 test case 思考全再动手。

• 【lower, nums[i] - 1】 范围内没有数, ADD;

• 【nums[last] + 1，upper】 范围内没有数, ADD;

• 动态更新 lower，维护当前有效 range.

时间复杂度 O(n).

public class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> list = new ArrayList<String>();
        for(int n : nums){
            int justBelow = n - 1;
            if(lower == justBelow) list.add(lower+"");
            else if(lower < justBelow) list.add(lower + "->" + justBelow);
            lower = n+1;
        }
        if(lower == upper) list.add(lower+"");
        else if(lower < upper) list.add(lower + "->" + upper);
        return list;
    }
}

Data Stream as Disjoint Intervals

作为一个 data structure design 题，首先要问好到底哪个 API call 比较频繁，设计上倾向于优化哪个操作。

先写了个略粗糙的版本，维护当前所有 interval 的 list，每次插入操作的时候靠 binary search 找每个 val 的位置，然后分情况考虑。

addNum(int val) 时间复杂度 O(log n) + O(n)

getInterval() 时间复杂度 O(1)

空间复杂度 O(n)

n = 当前有效数字个数

在测试数据集上，这个方法和 TreeMap 的做法用时不相上下。

public class SummaryRanges {
    List<Interval> list;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        list = new ArrayList<Interval>();
    }

    public void addNum(int val) {
        if(list.size() == 0){
            list.add(new Interval(val, val));
        } else {
            if(list.size() == 1){
                if(val <= list.get(0).end && val >= list.get(0).start){
                    return;
                }
            }

            if(val < list.get(0).start){
                if(val == list.get(0).start - 1){
                    list.get(0).start = val;
                } else {
                    list.add(0, new Interval(val, val));
                }
                return ;
            } else if (val > list.get(list.size() - 1).end){
                if(val == list.get(list.size() - 1).end + 1){
                    list.get(list.size() - 1).end = val;
                } else {
                    list.add(new Interval(val, val));
                }
                return ;
            }

            int pos = binarySearch(list, val);

            int prevEnd = list.get(pos).end;
            int nextStart = list.get(pos + 1).start;

            if(val <= prevEnd || val >= nextStart){
              return;  
            } else if(val == prevEnd + 1 && val == nextStart - 1){
                list.get(pos).end = list.get(pos + 1).end;
                list.remove(pos + 1);
            } else if(prevEnd + 1 >= val){
                list.get(pos).end = Math.max(list.get(pos).end, val);
            } else if(val == nextStart - 1){
                int newStart = list.get(pos + 1).start - 1;
                int newEnd = list.get(pos + 1).end;
                // Will have MLE if don't remove
                list.remove(pos + 1);
                list.add(pos + 1, new Interval(newStart, newEnd));
            } else {
                list.add(pos + 1, new Interval(val, val));
            }
        }
    }

    public List<Interval> getIntervals() {
        return list;
    }

    private int binarySearch(List<Interval> list, int val){
        int left = 0;
        int right = list.size() - 1;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            if(list.get(mid).start == val){
                return mid;
            } else if(list.get(mid).start < val){
                left = mid;
            } else {
                right = mid;
            }
        }

        return left;
    }
}

第二个版本，自己写了个 LinkedList 维护目前所有数字，每次 call getIntervals() 的时候根据 list 当场生成。

addNum(int val) 时间复杂度 O(n);

getIntervals() 时间复杂度 O(n);

空间：O(n);

n = 当前的有效数字个数。

public class SummaryRanges {
    private class Node{
        Integer val;
        Node next;
        public Node(Integer val){
            this.val = val;
            this.next = null;
        }
    }

    Node head;

    /** Initialize your data structure here. */
    public SummaryRanges() {
        Node dummy = new Node(null);
        head = dummy;
    }

    public void addNum(int val) {
        Node cur = head.next;
        Node prev = head;

        while(cur != null){
            if(cur.val == val) return;
            if(cur.val > val){
                prev.next = new Node(val);
                prev.next.next = cur;
                return;
            }
            prev = cur;
            cur = cur.next;
        }

        prev.next = new Node(val);
    }

    public List<Interval> getIntervals() {
        List<Interval> list = new ArrayList<Interval>();

        Node cur = head.next;
        Integer curStart = null;
        Integer curEnd = null;

        while(cur != null){
            int val = cur.val;
            if(curStart == null && curEnd == null){
                curStart = val;
                curEnd = val;
            } else {
                if(val == curEnd + 1){
                    curEnd = val;
                } else {
                    list.add(new Interval(curStart, curEnd));
                    curStart = val;
                    curEnd = val;
                }
            }
            cur = cur.next;
        }
        list.add(new Interval(curStart, curEnd));

        return list;
    }

}

参考了论坛代码之后，另一种巧妙的做法：

addNum(int val) 时间复杂度：O(log n)

getIntervals() 时间复杂度：o(n log n)

空间复杂度： O(n)

public class SummaryRanges {
    TreeMap<Integer, Interval> tree;

    public SummaryRanges() {
        tree = new TreeMap<>();
    }

    public void addNum(int val) {
        if(tree.containsKey(val)) return;

        Integer l = tree.lowerKey(val);
        Integer h = tree.higherKey(val);

        if(l != null && h != null && tree.get(l).end + 1 == val && h == val + 1) {
            // Joining two intervals
            tree.get(l).end = tree.get(h).end;
            tree.remove(h);
        } else if(l != null && tree.get(l).end + 1 >= val) {
            // Completely contained in left interval
            // Try to expand end
            tree.get(l).end = Math.max(tree.get(l).end, val);
        } else if(h != null && h == val + 1) {
            // Right next to right interval
            // Merge
            tree.put(val, new Interval(val, tree.get(h).end));
            tree.remove(h);
        } else {
            // Disjoint new interval
            tree.put(val, new Interval(val, val));
        }
    }

    public List<Interval> getIntervals() {
        return new ArrayList<>(tree.values());
    }
}

(FB) 给定的是 stream of intervals，求 cover range.

这么改了之后难了很多。。用 TreeMap 依然可以，但是假设目前 TreeMap 维护的都是 none-overlapping intervals，一个新 interval 加入之后可能会出现若干种情况：

• 完全被某个 interval 包含，无影响；

• 完全和其他 interval disjoint，插入即可；

• 和左边的 overlap，但是不和右边的 overlap;

• 和右边的 overlap，但是不和左边的 overlap;

• 一次跨了多个 interval，这里面就有全包括的，包括一半的，在左边搭边的，在右边搭边的。。。

于是我觉得这题用 TreeMap 比较和乎人性的做法是，TreeMap 只负责维护 sorted intervals，需要查询 coverage 的时候，直接 new ArrayList<>(treeMap.values()) 给导出来然后跑一遍 merge interval ..

或者，直接维护一个按照 start time 排好序的 disjoint list of intervals，然后每次新的 interval 过来的时候，就 in-place 扫一遍做 merge 好了~ 这样每次 insert O(N)，getCoverage O(1)

The Skyline Problem

扫描线算法，因为 building outline 只可能发生在每一段 "start/end" 的边界上，因此以每个 edge 的 (x, height) 排序，而后扫描。

• 当 x 值不同时，x 小的排在前面；

• else 当 y 值不同时，y 小的排在前面；

  • 调换的话下面的代码会有 bug

这题在九章课上讲的时候，使用的是 HashHeap，我们需要一个 maxHeap 来检测对于每一个点，我们建筑的最大高度，但同时在扫描过程中我们需要对每一个具体的 edge 进行删除操作，而 HashHeap 可以做到 O(log n) 的复杂度，Java 默认的 heap 只能做到 O(n).

如何在 heap 中快速删除这个问题和当初准备 Bloomberg 时候的马拉松问题一样，Java 中有现成的解决方案：

TreeMap.

接下来的问题是：

• 当遇到一座楼的右边界时，如何删除其对应的左边界？在 TreeMap 里直接用 Edge class 做 key 是不行的，因为我们无法通过 new 一个参数一模一样的 instance 去做 lookup. 所以在 Key-Value 的设计中，我们应该用 height 做 Key，因为同一座建筑左右墙 height 相等，就可以实现查找。即使有多座 height 一样的左墙，我们也只需要用 count 做 value，把当前 height 的墙数减一即可。

• 对于同一高度的不同建筑，如何确保其在 TreeMap 中不会互相 replace ，从而保证算法的正确性? 在自己 debug 的过程中，即使后面逻辑完全一致，不用负数 height 做 Key 依然会有 bug. ，用负数可以省去 Edge class 里面一个变量，最主要的是，在调用 Arrays.sort() 时，可以保证对于同一个 x 位置，在增加时永远先处理 height 最高的建筑，而删除时永远先删除 height 最小的建筑，从而保证了在同一个高度上多个建筑 Edge 重叠时，算法的正确性。

• 如何正确处理建筑清光之后，剩余高度为 0 的情况？一开始在 TreeMap 里加一个 (0, 1) 的 entry，代表始终有一个高度为 0 的墙，即地面；

O(Edge 排序) + O(Edge 数 * (插入 / 删除 + 查找))

O(2n log 2n) + O(2n * (log 2n + log 2n)) = O(n log n)

public class Solution {
    private class Edge implements Comparable<Edge>{
        int x;
        int y;

        public Edge(int x, int y){
            this.x = x;
            this.y = y;
        }

        public int compareTo(Edge b){
            // Ascending in x coordinate
            if(this.x != b.x) return this.x - b.x;
            else return this.y - b.y;
        }
    }

    public List<int[]> getSkyline(int[][] buildings) {
        // Key : height of edge
        // Value : count of edges of that height
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        List<int[]> list = new ArrayList<>();
        Edge[] edges = new Edge[2 * buildings.length];

        for(int i = 0; i < buildings.length; i++){
            int[] building = buildings[i];
            edges[i * 2] = new Edge(building[0], -building[2]);
            edges[i * 2 + 1] = new Edge(building[1], building[2]);
        }

        Arrays.sort(edges);
        treeMap.put(0, 1);
        int prevHeight = 0;

        for(Edge edge : edges){
            if(edge.y < 0){
                if(!treeMap.containsKey(-edge.y)){
                    treeMap.put(-edge.y, 1);
                } else {
                    int count = treeMap.get(-edge.y);
                    treeMap.put(-edge.y, count + 1);
                }
            } else {
                int count = treeMap.get(edge.y);
                if(count == 1){
                    treeMap.remove(edge.y);
                } else {
                    treeMap.put(edge.y, count - 1);
                }
            }

            int curHeight = treeMap.lastKey();
            if(prevHeight != curHeight){
                list.add(new int[]{edge.x, curHeight});
                prevHeight = curHeight;
            }
        }

        return list;
    }
}