`
lt200819
  • 浏览: 188065 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

重复区间问题

 
阅读更多

今天学习了一下重复区间问题

 

问题一,求最大重复区间个数

     1.数据是静态的:
        这个问题的最大重叠点一定出现在端点上。更进一步说,它一定可以出现在左端点上。
         对区间端点进行排序,N个区间排序后的端点数量为2N。
         遍历端点列表,左端点+1,右端点-1,记录遍历过程中的最大值,即为最大重复区间个数。
      2.数据是动态的:
          参考:算法导论中文版(原书第二版)190页思考题14-1
              http://bbs.csdn.net/topics/300181969

问题二,求最长重复区间长度

        首先还是将各行数据整理成x<y的标准形式,然后:

1)将各区间按照x从小到大排序(对于x(i)=x(i+1)这种情况可以优化,只保留较“长”的区间即可。比方说  此时有y(i)>y(i+1),那我们只需要保留[x(i),y(i)]区间,而对[x(i+1),y(i+1)]可以省略)——这一步需要O(n*logn);
2)将各区间数据进行整理,保持y严格递增,同时记录下被“删除”区间的最大长度max——这一步需要O(n);
(例如对于[1,5][2,4][3,5][4,7][5,6],为了保证y严格递增,需要删除某些区间,只剩下[1,5][4,7]
这一步的实际含义是统计区间相互“包含”的情况中,最长的“被包含”区间是多少);
3)经过前两步之后,在剩下的区间序列中,不管x还是y都是保持严格递增的(从而保证剩下的区间中不会再出现相互“包含”的情况)。
此时最长的重叠区间只可能有相邻的两个区间产生,遍历统计并更新max——这一步需要O(n)
从而整体只需要O(n*logn)的复杂度,主要花费在排序上。
如果对于已经排好序的数据而言,O(n)线性时间内即可完成。

 

分享到:
评论

相关推荐

    区间调度问题

    区间调度问题是一个经典的计算机科学问题,它涉及到在有限的时间资源内优化多个事件或任务的安排。这个问题在实际应用中非常广泛,例如会议安排、资源分配、任务调度等。本问题通常的目标是找到最大数量的任务,使得...

    快速生成特定区间内的不重复随机数(随机打乱区间元素顺序)

    在编程领域,生成特定区间内的不重复随机数是一项常见的任务,尤其在模拟、游戏开发、数据分析等场景中。本文将详细探讨如何通过移位和逻辑运算实现这一目标,以达到高效且准确的效果。 首先,我们要明确一点:生成...

    带权区间图的最短路算法

    5. **重复**:重复上述步骤直到无法再找到无效区间为止。 6. **计算最短路径**:基于最终的有效区间集合,利用如Dijkstra算法等传统方法计算出最短路径。 #### 性能分析 本算法的关键优势在于其时间复杂度为\(O(n ...

    重叠区间查找算法实现(C++)

    重叠区间查找算法是一种在计算机科学中用于处理和查找数据集中的重叠时间段的问题。这种算法在各种领域都有应用,例如日程管理、资源调度、生物信息学等。在这个C++实现的课程设计中,我们将深入探讨重叠区间查找...

    区间并集求解算法java实现

    2. 判断 如果 c 不属于 Z,那么把[c,d]加到 Z 中,…[am,am+1] ∪[c,d] ∪[am+2,am+3]…,然后从区间[c,d]开始遍历,去掉重复的部分。 3. 遍历集合 Z 的方法为,从某一个区间左端点开始,代码如下: 这个算法的实现...

    R语言区间估计实验报告

    置信水平(如95%或90%)表示在多次重复实验中,该区间能覆盖总体参数真实值的概率。 二、R语言的基本操作与区间估计 R语言是一款强大的统计分析软件,其丰富的统计包和可视化功能使得区间估计变得简单。在实验中,...

    C#——确定搜索区间的进退法

    每次迭代,我们都会将搜索区间一分为二,然后根据目标函数的性质排除掉一部分不可能包含最优解的子区间,重复这个过程直到找到满足精度要求的解。 在C#中,我们通常会定义一个类来封装这个问题,包括目标函数、搜索...

    教室课程调度问题的两种解法(区间着色问题)

    本主题聚焦于“教室课程调度问题”,这是一个经典的区间着色问题,属于组合优化的范畴。区间着色问题通常涉及如何用最少的颜色给一系列有重叠时间的区间着色,使得任意两个有重叠的区间不会被赋予相同的颜色,以此...

    erfenfa.rar_区间对分_区间算法_对分区间

    4. **迭代过程**:重复第2步和第3步,直到找到满足精度要求的零点或区间长度减小到某个预先设定的阈值。 区间对分法的优势在于其简单性和稳定性,因为它不需要函数的导数信息,对于某些不光滑或者不可微的函数依然...

    Oracle时间区间段合并.pdf

    本问题涉及的PDF文档“Oracle时间区间段合并.pdf”似乎提供了关于如何使用SQL来实现这一功能的方法。以下是对这个算法的详细解释: 首先,我们需要理解数据结构。在这个例子中,我们有一个名为`TAB_0`的表,包含`...

    定区间动轴法求区间最值.doc

    "定区间动轴法"是一种解决区间内二次函数最值问题的有效策略,尤其适用于高中数学中的函数和不等式部分。这种方法的核心在于将问题简化,将自变量所在的区间固定在数轴上,不论区间是否变动,都将其视为静态,然后...

    区间动态规划[定义].pdf

    区间动态规划的主要特点是将问题分解成多个子问题,然后使用动态规划来解决这些子问题。这种方法的优点在于可以减少计算的时间复杂度,提高算法的效率。 应用 区间动态规划有很多实际应用,例如: 1、凸多边形...

    XML文档的区间编码及结构连接

    例如,多谓词归并连接(Multi-Predicate Merge Join,MPMGJN)算法充分利用高速缓存,提高了命中概率,但仍然存在多次重复扫描的问题。Stack-Tree算法则通过将潜在连接的祖先节点存储在栈中,只需对AList和DList顺序...

    青蒿素高含量地区黄花蒿种质资源的简单重复序列区间归类.pdf

    青蒿素高含量地区黄花蒿种质资源的简单重复序列区间归类.pdf

    动态规划类型分析(区间,线性,树形,路径)

    它通过将大问题分解为相互重叠的子问题,然后利用子问题的最优解来构造原问题的最优解,避免了重复计算,从而提高了效率。本资料集合深入分析了四种主要类型的动态规划问题:区间、线性、树形和路径,并提供了相关...

    如何求置信区间(包括用Excel实现方法)

    - **置信区间**:在一定的置信水平下,如果我们重复多次抽样并计算置信区间,那么大约有这个置信水平的百分比的置信区间会包含总体参数的真实值。例如,95%的置信区间意味着在多次实验中,有95%的置信区间会包围住...

    第1章 区间类型动态规划 测试数据.rar

    在本压缩包中,"第1章 区间类型动态规划"可能包含了多个输入输出示例,用于验证你实现的动态规划算法是否能够正确解决各种区间问题。这些测试数据可能会覆盖不同的边界条件、复杂情况和特例,以确保你的解决方案全面...

    双正态总体均值的置信区间估计及MATLAB实现.pdf

    例如,当我们说95%的置信区间,就是指如果我们重复抽样并计算置信区间,大约有95%的置信区间会包含总体参数的真实值。置信区间的宽度取决于样本量和总体的变异程度,以及我们选择的置信水平。置信水平越高,置信区间...

    树状数组(Binary Indexed Tree,BIT)高效地处理动态的区间求和问题

    这种技术在处理具有大量重复数值的问题时尤为有效。 4. **动态规划:** 在某些动态规划问题中,树状数组可以用来优化状态转移过程,尤其是在需要频繁进行区间求和或更新的情况下。 5. **统计分析:** 当需要对数据...

Global site tag (gtag.js) - Google Analytics