LC 986. Interval List Intersections

https://leetcode.com/problems/interval-list-intersections/

问题是求解多个区间列表的重叠区间。一种办法是类似使用归并排序的算法，但是实现起来比较复杂，需要比较多的判断条件等。我这里有个实现, 处理两个列表好像还行，但是要处理三个或者是多个的话，就特别容易处理。

另外一个方法是参考会议室问题的实现，将区间分解成为起始和终止两个点并且进行排序，然后将这些点当做事件来进行处理。处理这些事件的方法是：

遇到入点将depth+1，遇到出点将depth-1.
遇到入点如果depth==k(区间列表), 可以认为当前点被所有区间都覆盖了，先记录下来保存为last。
遇到出点如果depth==k的话，那么[last, p]就是一个被所有区间都覆盖的区间。

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        if not A or not B:
            return []

        K = 2
        xs = []
        xs += [(A[i][0], 0) for i in range(len(A))]
        xs += [(A[i][1], 1) for i in range(len(A))]
        xs += [(B[i][0], 0) for i in range(len(B))]
        xs += [(B[i][1], 1) for i in range(len(B))]
        xs.sort()

        ans = []
        last = None
        depth = 0
        for p, d in xs:
            if d == 0:
                depth += 1
                if depth == K:
                    last = p
            else:
                depth -= 1
                if last is None:
                    continue
                assert depth == K - 1
                ans.append([last, p])
                last = None
        return ans