986. Interval List Intersections-LeetCode

Posted on In

题目：Interval List Intersections
难度：Medium

Description

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

题目意思大致就是，给了两列闭区间集合，然后一对一对的计算其交集。
以下面这个为例：
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
图示：

这题要注意的是，它要求的并不是你拿一个我拿一个，逐个比较，计算交集，我的第一次提交就没有注意到这一点，而且两列list的长度并不相同，在比较的时候，应该是谁的右值更大，谁就留下来继续比较，知道另一方拿不出元素来比较为止，这就很简单了： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        result = []
        if (len(A) == 0 or len(B) == 0):
            return result
        i = 0
        j = 0
        while i < len(A) and j < len(B):
            minValue = max(A[i][0], B[j][0])
            maxValue = min(A[i][1], B[j][1])
            if minValue <= maxValue:
                result.append([minValue, maxValue])
            if A[i][1] > B[j][1]:
                j += 1
            else:
                i += 1
        return result

发现和最快的几个算法代码类似，开心！！！