接外包,有相关需求的可以联系我:Telegram | Email

Interval List Intersections

该文章创建(更新)于04/11/2022,请注意文章的时效性!

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

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 are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

  • [Interval List Intersections](Interval List Intersections)

Solution

  • submit code
class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        intput = firstList + secondList
        # 先index0排序
        intput.sort(key=lambda x: x[0])
        # indexo相同时,index1降序
        for x in range(len(intput) - 1):
            if intput[x][0] == intput[x+1][0] and intput[x][1] < intput[x+1][1]:
                intput[x][1],intput[x+1][1] = intput[x+1][1],intput[x][1]


        # base case
        if len(intput) == 1:
            return intput

        left = intput[0][0]
        right = intput[0][1]

        ret = []

        for x in  range(1,len(intput)):
            # 部分重叠时
            # little overlap
            if intput[x][0] <= right and intput[x][1] >= left and intput[x][1] >= right:
                ret.append([intput[x][0],right])
                left = right
                right = intput[x][1]
            # 覆盖时
            # cover
            elif intput[x][0] >= left and intput[x][1] <= right:
                ret.append([intput[x][0],intput[x][1]])
                left = intput[x][0]
            # 没有重叠时
            # no overlap
            elif intput[x][0] > right:
                left = intput[x][0]
                right = intput[x][1]


        return ret        
  • full code
class Solution:
    def intervalIntersection(self, firstList, secondList):
        intput = firstList + secondList
        # 先index0排序
        intput.sort(key=lambda x: x[0])
        # indexo相同时,index1降序
        for x in range(len(intput) - 1):
            if intput[x][0] == intput[x+1][0] and intput[x][1] < intput[x+1][1]:
                intput[x][1],intput[x+1][1] = intput[x+1][1],intput[x][1]

        print(intput)

        # base case
        if len(intput) == 1:
            return intput

        left = intput[0][0]
        right = intput[0][1]

        ret = []

        for x in  range(1,len(intput)):
            print("x:",x,"left:",left,"right:",right,"intput[x][0]:",intput[x][0],"intput[x][1]:",intput[x][1])
            # 部分重叠时
            # little overlap
            if intput[x][0] <= right and intput[x][1] >= left and intput[x][1] >= right:
                ret.append([intput[x][0],right])
                left = right
                right = intput[x][1]
            # 覆盖时
            # cover
            elif intput[x][0] >= left and intput[x][1] <= right:
                ret.append([intput[x][0],intput[x][1]])
                left = intput[x][0]
            # 没有重叠时
            # no overlap
            elif intput[x][0] > right:
                left = intput[x][0]
                right = intput[x][1]


        return ret

S = Solution()
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,9],[15,24],[24,28]]
print(S.intervalIntersection(firstList,secondList))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/04/11/interval-list-intersections/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码