精华内容
下载资源
问答
  • 题目描述: 给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, ...两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,

    题目描述:

    给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。

    返回这 两个区间列表的交集 。

    形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b 。

    两个闭区间的 交集 是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

    解题思路:

            本题可以使用双指针方法,运用两个指针分别从左到右遍历两个列表,不断寻找重复区间。本题重点个人认为在两个方面1.如何判断两个区间是否重叠,若重叠该怎么返回重叠的部分。2.在对两个区间进行操作后(无论两区间是否重叠),如何寻找新的两个区间进行对比。

            1.对于第一方面,能发现,若两个区间有重叠的部分,则重叠部分的左边界为两个区间左边界中较大的那个边界(记作left);重叠部分的右边界为两个区间右边界中较小的那个边界(记作right)。若left<=right,则[left,right]便是重叠区间;若left>right,则两个边界没有重叠。

            2.当我们完成两个区间重叠部分的查找后,接下来就是选择两个新的区间进行判断。选取规则为:保持原本两个区间中右边界较大的那个区间,右边界较小的那个区间换成它所在的列表的下个区间。对新的两个区间重复1,2两步,直到某个指针走到结尾为止。

            举例:

            在找出firstList[i]区间和secondList[j]区间的重叠区域后,假设secondList[j][1]>firstList[i][1],此时secondList[j]区间的右边界大于firstList[i]的右边界,因此下一步就是要找出firstList[i+1]和secondList[j]的重叠区域。

    (反过来,如果保留的是右边界较小的区间,即firstList[i]和secondList[j+1],那么之后将永远找不到重叠区间)

    代码如下:

        public  int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
            int i=0;
            int j=0;
            int left;//重叠区间的左边界
            int right;//重叠区间的右边界
            ArrayList<int[]> res=new ArrayList<>();
            while (i<firstList.length && j<secondList.length){
                left=Math.max(firstList[i][0],secondList[j][0]);
                right=Math.min(firstList[i][1],secondList[j][1]);
                if(left<=right) res.add(new int[]{left,right});
                if(firstList[i][1]>=secondList[j][1]){
                    j++;
                }else {
                    i++;
                }
            }
            return res.toArray(new int[res.size()][2]);
        }

           

    展开全文
  • 问题描述:给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的...两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)示例:输入:A = [[0,2],[5,10],[...

    问题描述:

    给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。

    返回这两个区间列表的交集。

    (形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

    示例:

    输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]

    输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

    注意:输入和所需的输出都是区间对象组成的列表,而不是数组或列表。

    提示:

    0 <= A.length < 1000

    0 <= B.length < 1000

    0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

    代码:

    classSolution:def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) ->List[List[int]]:

    res=[]

    i= j =0while i < len(A) and j

    lo=max(A[i][0], B[j][0])

    hi= min(A[i][1], B[j][1])if lo <=hi:

    res.append([lo, hi])if A[i][1] < B[j][1]:

    i += 1

    else:

    j += 1

    return res

    核心就是标红的一段:比如

    A = [[0,2],[5,10],[13,23],[24,25]]

    B = [[1,5],[8,12],[15,24],[25,26]]

    [0,2]和[1,5]之间2比5小,那么A中的下一个数组就可能与[1,5]有交集,所以让指向A的指针+1。反之让指向B的指针+1.

    结果:

    原文:https://www.cnblogs.com/xiximayou/p/12354227.html

    展开全文
  • leetcode 986. 区间列表的交集 ...两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。) 示例: 输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,1

    leetcode 986. 区间列表的交集

    给定两个由一些 闭区间 组成的列表,每个区间列表都是成对不相交的,并且已经排序。
    返回这两个区间列表的交集。
    (形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)
    示例:
    在这里插入图片描述

    输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
    输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
    

    提示:

    0 <= A.length < 1000
    0 <= B.length < 1000
    0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

    思路

    由于区间已经排好序,所以先拿出A中的第一个区间和B中第一个区间,判断有没有交集,选取左端点的最大值作为start和右端点的最小值作为end,如果start<=end,那么就存在交集,将其放到结果文件中,然后判断A中的第一个区间和B中第一个区间那一个比较长,也就是右端点哪一个较大,如果A大,那么选取B的下一个,如果B大,那么选取A的下一个,依次比较即可.

    好了,看代码

    class Solution:
        def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
            m = len(A)
            n = len(B)
            p1 = 0
            p2 = 0
            res = []
            while p1 < m and p2 < n:
                a1 = A[p1][0]
                a2 = A[p1][1]
                b1 = B[p2][0]
                b2 = B[p2][1]
                
                start = max(a1, b1)
                end = min(a2, b2)
                if start <= end:
                    res.append([start, end])
                if a2 < b2:
                    p1 += 1
                else:
                    p2 += 1
            return res
    
    

    leetcode 56. 合并区间

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3][2,6] 重叠, 将它们合并为 [1,6].
    

    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4][4,5] 可被视为重叠区间。
    

    思路

    首先将区间按照左端点大小进行排序,然后现将第一个区间放到结果res中,然后遍历后面的区间,如果当前区间的左端点比结果res的最后一个区间的右端点小 inter[0] <= res[-1][1],那么会产生重合区间,重叠区间的左端点是res中最后一个区间的左端点left = res[-1][0],重叠区间的右端点是当前区间和res最后一个区间的右端点的最大值right = max(res[-1][1], inter[1]),之后将res[-1]从结果中删除,将重叠区间放进去,如果当前区间的左端点比结果res的最后一个区间的右端点大,那么不可能产生重叠,直接将区间放进res中

    好了,看代码

    class Solution:
        def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            res = []
            if not intervals:
                return res
            intervals.sort()
            res.append(intervals[0])
            for inter in intervals[1:]:
                if inter[0] <= res[-1][1]:
                    left = res[-1][0]
                    right = max(res[-1][1], inter[1])
                    res.pop()
                else:
                    left = inter[0]
                    right = inter[1]
                res.append([left, right])
            return res
    

    leetcode 57. 插入区间

    给出一个无重叠的 ,按照区间起始端点排序的区间列表。
    在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
    示例 1:

    输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
    输出:[[1,5],[6,9]]
    

    示例 2:

    输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
    输出:[[1,2],[3,10],[12,16]]
    解释:这是因为新的区间 [4,8][3,5],[6,7],[8,10] 重叠。
    

    思路

    由于,区间是排好序的,所以可以先找到开始重叠的区间位置temp,对于重叠之前的区间保持不变,当发生重叠时,进行区间的合并,,直到后面的区间不再重叠,此时可以删除中间重叠部分的区间,最后将合并好的区间插入到temp位置
    区间分为三段
    第一段为前半部分不重叠的,判断条件为:intervals[i][1] < newInterval[0]
    第二段为重叠部分,判断条件为:intervals[i][0] <= newInterval[1]并且intervals[i][1] >= newInterval[0]
    第三部分为后半部分不重叠的,判断条件为:intervals[i][0] > newInterval[1]

    class Solution:
        def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
            if not newInterval:
                return intervals
            if not intervals:
                return [newInterval]
            i = 0
            length = len(intervals)
            while i < length and intervals[i][1] < newInterval[0]: # 前半部分不重叠的
                i += 1
            temp = i # 记录开始重叠的位置
            while i < length and intervals[i][0] <= newInterval[1]: # 出现重叠,注意此时可以省略intervals[i][1] >= newInterval[0]这个条件,因为上一个while循环已经结束了
                newInterval[0] = min(intervals[i][0], newInterval[0])
                newInterval[1] = max(intervals[i][1], newInterval[1]) # 更新重叠区间的数值
                i += 1
                
            # while 循环终止,说明不再出现重叠,也即intervals[i][0] > newInterval[1]
            del intervals[temp:i] # 删除中间重叠的区间
            intervals.insert(temp, newInterval) # 将合并好的区间插入到temp位置
            return intervals
    
    展开全文
  • 问题描述:给出一个重叠的 ,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。示例1:输入: intervals = [[1,3],[6,9]], new...

    问题描述:

    给出一个无重叠的 ,按照区间起始端点排序的区间列表。

    在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

    示例 1:

    输入: intervals = [[1,3],[6,9]], newInterval = [2,5]

    输出: [[1,5],[6,9]]

    示例 2:

    输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

    输出: [[1,2],[3,10],[12,16]]

    解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

    有了之前leetcode56的思路,这就简单了,直接先将要插入的区间加入到intervals中,后面代码都是一样的。

    classSolution:def insert(self, intervals: List[List[int]], newInterval: List[int]) ->List[List[int]]:

    res=[]

    intervals.append(newInterval)

    intervals.sort()for i inintervals:if not res or res[-1][1]

    res.append(i)else:

    res[-1][1]=max(res[-1][1],i[1])return res

    结果:

    这是我第二次运行的结果,记一次时间消耗为156ms,击败7%,不知道它的运行机制是怎样的,还是根据自己电脑有关。

    再仔细看下题目,说了intervals是按区间端点进行排序的,因此,可以利用二分查找法查找该区间插入的位置。

    classSolution:def insert(self, intervals: List[List[int]], newInterval: List[int]) ->List[List[int]]:if notintervals:return[newInterval]

    res=[]

    ins=self.helper(intervals,newInterval[0])

    intervals.insert(ins,newInterval)for i inintervals:if not res or res[-1][1]

    res.append(i)else:

    res[-1][1]=max(res[-1][1],i[1])returnresdefhelper(self,intervals,val):

    l=0

    r=len(intervals)-1

    if intervals[-1][0]

    if intervals[0][0]>val:returnlwhile l

    mid=(l+r)//2

    if intervals[mid][0]>val:

    r=midelse:

    l=mid+1

    return l

    结果:

    注意要考虑特殊情况,当插入的区间端点大于被插入区间端点的最大值时,要返回len(intervals) ,即插入到被插入区间最后面。

    展开全文
  • 给若干个区间区间数少于1000,区间范围[-10000,10000]。当区间数少于2时输出None。 当各个区间交集的时候取交集,再求交集的并集 样例输入 1 3 2 4 4 8 5 9 样例输出 2 3 4 4 5 8 说明 [1,3]、[2,4]、[4,8]...
  • 前缀和技巧区间问题1、区间的交集1.1、题目1.2、思路1.3、题解2、区间的并集2.1、题目2.2、思路2.3、题解 ...两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]
  • 循环判断两个区间是否重叠(对于很多元素的对比,化简的思路是先只看两个元素怎么比较,然后循环迭代) 重叠则找max end;不重叠则加入个新区间元素 抽象模式 intervals.sort(<排序>) for <进入循环&g...
  • 题目 题目链接 一本通OJ:http://ybt.ssoier.cn:8088/problem_show.php?pid=1236。 ... ...给定 n 个闭区间 [ai; bi],其中 i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为闭区间。例如,[1;2] 和 [2;3] ...
  • 问题描述:给定n位正整数a,去掉其中任意k≤n数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。 输入: 6579431483 ...
  • 3 区间交集

    2021-05-06 23:05:46
    986. 区间列表的交集 给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj,...两个闭区间交集一组实数,要么为空集,要么为闭区间。例
  • 贪心算法——区间问题

    千次阅读 2019-04-06 16:09:36
    数轴上有N个闭区间[Ai, Bi]。取尽量少的点,使得每区间内都至少有一个点(不同区间内含的点可以是同一个)。 输入 第1行:一个整数N 接下来N行,每行2整数Ai,Bi 输出 一个整数,表示满足条件的最少点数。 样例...
  • 区间覆盖问题

    2018-08-19 22:33:42
    问题描述:给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖。   样例: 区间长度8,可选的覆盖线段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3...
  • 我从来不是一个呆在舒适区间的人,高中毕业,大学往死了干了三年,毕竟还是要靠实力说话啊,努力、自制、对照下,喜欢呆在舒适区间里人,没紧迫感、没压力、不思进取、“人无远虑必有近忧”的人。这么想,我好像也...
  • 、Problem ...两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。) 输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]
  • 区间调度问题重叠区间、区间合并以及求区间交集。 解决区间问题的一般思路是先排序,再操作。关于排序方式的选择,不同的题型选择而不同的排序方式: 对于重叠区间问题,往往是和贪心策略有关,因此根据右端点...
  • 区间问题 LeetCode

    2021-01-14 15:28:52
    给出一个区间的集合,请合并所有重叠区间。 示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: ...
  • 两个闭区间交集一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。) 示例: 输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
  • 重叠区间的个数

    千次阅读 2016-12-09 22:11:20
    题目:给定可能的重叠区间,找出重叠区间的个数。 伪代码:区间的定义如下:class Interval{ int start; //起点 int end; //止点 Interval (int a,int b){ start =a; end = b; } }首先,要定义区间的类...
  • 本节记录了贪心算法的三类区间问题:互不相交,区间覆盖,区间选点。按照自己的思路进行了一定的解析。较为简单,不说废话了
  • Leetcode-区间问题

    2021-12-31 18:24:01
    请你合并所有重叠区间,并返回一个重叠区间数组,该数组需恰好覆盖输入中的所有区间。 解题思路 思路 如果我们按照区间的左端点排序,那么在排完序的列表中,可以合并的区间一定是连续的。如下图所示,标记为...
  • 关于区间相关这类问题,基本思路都是排序,然后找交集或者找合集。首先要做的是讨论区间之间的包含情况,都画出图,决定是end还是start排序。 文章目录1. 最多不相交区间【题目描述】终点排序起点和终点排序的不同之...
  • 给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。 返回这两个区间列表的交集。 示例: 输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] 输出:[[1,2...
  • 给你两个版本号 version1 和 version2 ,请你比较它们。 版本号由个或多个修订号组成,各修订号由个 ‘.’ 连接。每个修订号由 多位数字 组成,可能包含 前导零 。每个版本号至少包含个字符。修订号从左到右...
  • 区间问题

    2020-09-21 15:26:38
    题意: 给定N个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。1≤N≤105,−109≤ai≤bi≤109 题解: 本题按照区间...
  • 给定N个闭区间,将有重叠部分的区间合并,求最后得到的(那些)区间 输入 第行整数N,其后N行,每行两个整数l,r,描述个区间,输入只有一组 输出 每行两个数,为个区间的左右边界,按左边界升序输出每个区间...
  • Pattern: Merge Intervals,区间合并类型 介绍部分来源: 链接:...给两个区间个是a,另外个是b。别小看就两个区间,他们之间的关系能跑出来6种情况。详细的就看图啦。 理解和识别这六种情况,
  • 给出一个重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 链接:...
  • 区间贪心

    2020-04-18 14:08:22
    给定N区间(x, y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。 比如(1, 3)、(2, 4)、(3, 5)、(6, 7),可以选择最多三个区间(1, 3)、(3, 5)、(6, 7),它们互相没有交集。 贪心策略:考虑最简单情况...
  • 牛客

    万次阅读 2020-06-30 11:10:07
    最大括号深度 现有字符串仅由 '(',')','{','}','[',']'六种括号...一个只包括 '(',')','{','}','[',']'的字符串 输出描述: 一个整数,最大的括号深度 示例2 输入 ([]{()}) 输出 3 按索引...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 197
精华内容 78
关键字:

区间重叠问题给定一组闭区间,其中部分区间存在交集。任意两个给定区间的交集,称

友情链接: TEXTEDIT.rar