986. Interval List Intersections

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

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

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

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