区间列表交集

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param first int整型二维数组
# @param second int整型二维数组
# @return int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/20dce144f04f4db298fbb3349e9d93ec?tpId=196&tqId=40521&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        双指针遍历first、second两个列表，取交集。本题的关键在于取交集之后的区间移动问题。换句话说，first中的一个区间，可能与second中连续好几个区间都有交集，对于这种场景的处理，才是本题考查的关键。比如fisrt = [[1, 10]], second = [[0, 2], [3, 4], [6, 8]]，其交集为[[1, 2], [3, 4], [6, 8]]
    复杂度：
        时间复杂度：O(min(m, n))
        空间复杂度：O(1)
    """

    def intersectionofintervals(self, first, second):
        # write code here
        m, n = len(first), len(second)

        i, j = 0, 0
        x1, y1, x2, y2 = -1, -1, -1, -1
        res = []
        while i < m and j < n:
            x1, y1 = max(x1, first[i][0]), max(y1, first[i][1])  # 当前访问的first区间
            x2, y2 = max(x2, second[j][0]), max(y2,
                                                second[j][1])  # 当前访问的second区间

            if x1 <= x2:  # [x1, y1] 在 [x2, y2]左侧
                if y1 < x2:  # 无交集
                    i += 1
                else:  # y1 > x2，有交集，交集为 [x2, min(y1, y2)]
                    intersection = [x2, min(y1, y2)]
                    res.append(intersection)
                    if y1 == y2: # 区间移动
                        i += 1
                        j += 1
                    elif y1 > y2:
                        j += 1
                        x1 = y2
                    else:  # y1 < y2
                        i += 1
                        x2 = y1
            else:  # x1 > x2, [x2, y2] 在 [x1, y1]的左侧
                if y2 < x1:  # 无交集
                    j += 1
                else:  # y2 > x1，有交集，交集为 [x1, min(y1, y2)]
                    intersection = [x1, min(y1, y2)]
                    res.append(intersection)
                    if y1 == y2: # 区间移动
                        i += 1
                        j += 1
                    elif y1 < y2:
                        i += 1
                        x2 = y1
                    else:  # y1 > y2
                        j += 1
                        x1 = y2

        return res


if __name__ == "__main__":
    sol = Solution()

    first, second = [[0, 2], [5, 10], [11, 13]], [[1, 3], [5, 11]]

    res = sol.intersectionofintervals(first, second)

    print res