java 多个区间重叠算法,区间形成闭环的算法问题

系统界面有多个输入框 比如
1:>24
2: <5
3: 大于等于5 并且小于等于24

真实环境 可能不仅仅是三个区间 可能是更多区间 ,但是要求所有的区间是闭环的,并且区间是不能叠的

比如 如果上面三个区间 改为
1:>=24
2:小于等于5

3:大于等于5 并且小于等于24

改为这样的三个区间的话 就错了 因为等于5 和 等于24 有重叠了

同时用户输入的区间 还要形成一个闭环 比如 下面这三个就形成一个闭环
1:>24
2: 小于5
3: 大于等于5 并且小于等于24

如果改成
1:>24
2:<5
3:大于5 并且小于24
这样就不形成闭环了,因为没有包括 5 和 24 就提示用户输入错误。

现在求一个算法 来判断用户输入的多个区间 不能重叠,同时还要校验用户输入的区间是一个闭环?
有案例代码 最好

5个回答

上一条少一个字“点”

重叠算法就是上面写的,对于形成闭环的,在上面一步的基础上再进行遍历判断就可以了,伪代码我就不写了,说下方法

把任一区间一个点和其它所有区的点进行比较,必须有相同数值的两个点且这两个区间点必须是互补,遍历所有点就可以了。
我所说的互补是这样的,如一个区间是>5,那么另一个区间点必须是<=5

ljz0898
追梦少年888 感谢
一年多之前 回复

二重for循环,用一个区间与其它所有区间进行比较是否重叠,如果有重叠结束

for(int i= 0; i < 区间总数;i++)
{

    for(int j = i+1; j < 区间总数;j++)
    {
        if(区间[i]非闭区间或者区间[j]非闭区间)
            retrun;
        if(区间[i]和区间[j]重叠)
            return;
    }

}

不好意思,看错一个需求。要求是所有区间连起来就是没有区间吧?

ljz0898
追梦少年888 是的 是所有区间连起来 形成一个闭环 而不是单个区间
一年多之前 回复

是的 是所有区间连起来 形成一个闭环 而不是单个区间

形成闭环这个也是一个复杂的算法 想了 快一天了 还没有想起来

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
给出多个可能重叠的区间,找出重叠区间的个数。
import java.util.Arrays; class Interval{ int start; int end; Interval(int a,int b){ start = a; end = b; } } class Point implements Comparable{ int value; int type; Point(int v,in
区间树上重叠区间查找
区间树上重叠区间查找 本次试验是在红黑树的基础上扩展数据结构
【算法】求两个区间的重叠长度
已知数轴上的两个区间:R1的起点是min1,区间长度len1,R2的起点是min2,区间长度len2,求这两个区间的重叠长度,若不重叠,求他们之间的距离
leetcode 重叠区间问题
重叠区间问题可以总结为在坐标轴上若干个位置为 (start(i),end(i))的区间,要求求解这些区间中有多少个不重叠区间,或者合并重叠的区间。 leetcode有大神总结了通用模板,点这里 该问题分两类:第一类求重叠区间个数(leetcode 452,435),第二类求合并后的区间(leetcode 56,763)。 对于第一类问题,通常按照end排序,维护一个end变量即可。 低于...
重叠区间问题
题目描述:请编写程序,找出下面 “ 输入数据及格式 ” 中所描述的输入数据文件中最大重叠区间的大小。 rn对一个正整数 n ,如果 n 在数据文件中某行的两个正整数(假设为 A 和 B )之间,即 A<=n<=B 或 A>=n>=B ,则 n 属于该行;如果 n 同时属于行 i 和 j ,则 i 和 j 有重叠区间;重叠区间的大小是同时属于行 i 和 j 的整数个数。 rn例如,行( 10 20 )和( 12 25 )的重叠区间为 [12 20] ,其大小为 9 ;行( 20 10 )和( 12 18 )的重叠区间为 [10 12] ,其大小为 3 ;行 (20 10) 和( 20 30 )的重叠区间大小为 1 。 在标准输出上打印出输入数据文件中最大重叠区间的大小,如果所有行都没有重叠区间,则输出 0 。 rnrnrn给点思路吧~~~~rn
区间重叠问题 (贪心)
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the
非线性方程的区间算法
区间分析,又称区间数学,是一门用区间变量代替点变量进行运算的数学分支,本书主要介绍了用区间分析方法求解非线性方程的方法
【ACM】区间并算法
#include &amp;amp;lt;iostream&amp;amp;gt; using namespace std; struct Node { int left, right; int father; }node[1000]; bool Judge(int a, int b) { if(node[b].left &amp;amp;gt;= node[a].right || node[b].right &amp;amp;lt...
关于区间过滤的算法
问题基本是这样的: 现有一由闭区间组成的数组 rn过滤条件如下:rn对于所有区间之间的关系rn1.包含与被包含关系的:保留包含的rn2.有交集的:保留区间范围大的,如果区间范围相同 保留区间中数值大的 (相接的除外)rn3.独立的(以上两种情况之外的)保留rnrn求最简算法
【算法笔记】区间贪心
贪心 对于贪心问题,不要太关注过程或者方法,而应该关注结果的数据。 一般来讲,贪心问题至少要讨论两种情况。 大多数时候, 贪心 = 预处理 + 贪心算法, 例如排序, 或某种数学处理. 往往真正的贪心算法其实不难, 一般都是取某个值的最大最小 排序: 大于大的在前, 小于小的在前 贪心问题, 要优先考虑思维, 其次再从思维入手考虑具体的算法 区间贪心 一、线段覆盖 n个开区间(ai,bi),选择尽...
区间值比较算法
/** * @author 孟令杰 * @time 2017年9月28 */ package com.system.utils; import java.math.BigDecimal; public class CarConsumScoreUtils { private Integer purchaseScore;//购车费用评分 private Integer upkeepSco
java数字区间重叠校验
一、    设计背景 在具体的软件开发过程中可能会涉及到用两个数字表示一定的数字区间范围,或者是一个数字,另一个数字是无穷大或者是无穷小的数字区间范围。其实,总结起来共有8种类型的数字区间,它们是:1、左闭,右边为无穷大的区间;2、右闭,左边为无穷小的区间;3、左开,右边为无穷大的区间;4、右开,左边为无穷小的区间;5、左闭右闭区间;6、左闭右开区间;7、左开右闭区间;8、左开右开区间。在实际应...
算法-二叉查找树-搜索区间
题目:给定两个值 k1 和 k2(k1 样例 如果有 k1 = 10 和 k2 = 22, 你的程序应该返回 [12, 20, 22]. 20 / \ 8 22 / \ 4 12 代码如下: 类似中序遍历,加上区间的筛选。 /**  * Definition of TreeNode:  * public class T
算法-区间的比较
#include&amp;lt;iostream&amp;gt; #include&amp;lt;vector&amp;gt; #include&amp;lt;list&amp;gt; #include&amp;lt;algorithm&amp;gt; #include&amp;lt;functional&amp;gt; using namespace std; //设计一个函数对象 bool bothEvenOrOdd(int elem1, int elem2) { ...
RMQ算法:区间最小值
假如一系列的查询数组区间的最小值,使用暴力遍历的话,最坏情况是O(n^2),而RMQ算法运用动态规划以及位运算的方法,预处理的时间复杂度为O(nlogn),查询时间复杂度为O(1),代码如下: //rmq算法是解决区间最小值问题的,预处理的时间复杂度是nlog(n),查询时间是O(1) #include&amp;lt;iostream&amp;gt; #include&amp;lt;vector&amp;gt; #inclu...
算法笔记_区间贪心
即所谓的区间不相交问题:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两没有交集,问最多找到多少个区间? 思路:总选择左端点最大的区间,若左端点一样,就选右端点最小的. 给出如下实例代码: #include&amp;lt;iostream&amp;gt; #include&amp;lt;stdlib.h&amp;gt; #include&amp;lt;algorithm&amp;gt;//algorithm意为&quot;算...
算法之插入区间
给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 示例 2: 输入: intervals = [[1,2],[3,5],[6,7],[8,10],...
区间求交集算法
最近要去网易笔试,做往年笔试题的时候遇到一个比较难搞的,原题:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]} 在网上看了一下没有比较巧妙地解决方案,于是自己想了一个,思路如下,我假设了两个区间集合A{[2,4],[8,14],[15,20],[22,25]},B{[1,5],[8,16],[19,
js区间算法
var obj = [ ms: "8:00", me: "9:00" , ms: "10:00", me: "15:00" , ms: "10:30", me: "16:00" , ms: "11:30", me: "14:00" , ms: "15:30", me: "16:30" , ms: "17:30", me: "19:00" ]rnrnvar obj1=[ ms: "8:00", me: "11:00" , ms: "10:00", me: "15:00" , ms: "12:00", me: "15:00" ]rnrnvar obj2=[ ms: "8:00", me: "10:00" , ms: "9:00", me: "11:00" , ms: "10:00", me: "12:00" , ms: "11:00", me: "13:00" , ms: "12:00", me: "14:00" ];rnrnvar obj3=[ ms: "8:00", me: "10:00" , ms: "9:00", me: "11:00" , ms: "12:00", me: "14:00" , ms: "15:00", me: "16:00" , ms: "17:00", me: "19:00" , ms: "18:00", me: "20:00" ]rnrn这样四组数据要一个方法rnfunction getArr(arr) return ??? rn时间重合的对应的有几个分别是那几个rnrn返回这样的数组,怎么做,求大神结局给思路rn//[1,4,4,4,41]rn//[3,3,3]rn//[5,5,5,5,5]rn//[2,2,1,1,2,2]rn
1091 线段的重叠 区间重叠
题目链接思路 保证思路的有序性。 如果拿出来每一条边与其他边进行比较,那么一定可以得出答案。 但是一条边[l,r]只能和与它有交集的边产生可能。那么进行排序,按照左端点,在某条边的l大于当前选择的边的r时break。 能否在O(n)的算法处理呢? 也就是说,枚举的区间是有选择性的。假设当前选定的区间是A。 那么之后的区间有ECDE四种情况,再加上 无交集的情况。 1.如果是B,C,E,
区间树上的重叠区间查找算法源代码和实验报告
区间树上的重叠区间查找算法源代码和实验报告
算法导论——区间树上的重叠区间查找算法
一、   算法设计与分析: (1)   数据结构设计: //区间 struct Interval{ int low; int high; }; //节点 struct Node{ Node(int low,int high){ this->key=low; this->Int.low=low; this
区间树上的重叠区间查找算法——C++
区间树上的重叠区间查找算法——C++ 题目: 区间树的构造; 查找算法Interval-Search(T, i); 算法设计:      步骤一:区间树是在红黑树基础上进行的简单的数据结构扩张。选择一棵红黑树,在每个结点x中加入一个区间属性x.int,设置x的关键字为区间的低端点x.int.low。      步骤二:附加信息。附加的信息为x.max,其值为以x为根的子树中所有区间的端点...
最大重叠区间的个数
只要将区间分隔成各个点,每个点有两个属性,一个是值,一个是标志(0起点,1止点),然后对这些点排序,最后,从头开始扫描排序的结果,遇到起点重叠个数加1,遇到止点重叠个数减1,并且记录好重叠个数的最大值。,因为算法时间主要消耗在排序上。摘抄自http://blog.csdn.net/s634772208/article/details/46492651 我是根据http://blog.csdn.ne...
435. 无重叠区间
435. 无重叠区间 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没有重叠。 示例 2: 输入...
贪心------无重叠区间
给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没有重叠。 示例 2: 输入: [ [1,2], [1,2], [1,2] ]...
求解重叠区间
方法一: 对于给定的两个区间(a,b)和(c,d),显然,当且仅当a≤d&amp;&amp;c&lt;=b时才会有重叠区间, 此时重叠区间长度L为 L=min(b,d)−max(a,c) 方法二: 建立一个区间段数组,例如[a,b),将[a,a+1)...[b-1,b)的区间段加1,[c,d),将[c,c+1)...[b-1,b)的区间段加1,最后统计为2的区间数量即...
重叠区间个数
问题:给定多个可能重叠的区间,找出重叠区间的个数。 例如: 输入:[1,5],[10,15],[5,10],[20,30] 输出:3 时间复杂度O(nlogn) OC算法实现: /** 6 */ #import //区间点对象 @interface IntervalPoint : NSObject @property (nonatomic,assign) int value;
区间树的重叠区间查找算法
算法导论,在红黑树的基础上扩张出区间树的数据结构,并且构造区间树的重叠区间查找算法。
LeetCode435. 无重叠区间
LeetCode上提交 执行时间优于100%的提交记录   给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区间...
区间重叠的合并模板
struct Day { ll l,r; } day[N]; for(int i=1; i<n; i++) { if(day[i].l<=day[cnt].r+1) day[cnt].r=max(day[cnt].r,day[i].r); else { da
无重叠区间
无重叠区间 算法描述:给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没有相互重叠。 示例如下: 示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没有重叠。 示例 2:...
重叠区间的个数
给定多个可能重合的区间,找出重叠区间的个数。 题解: 我们首先根据区间点的不同类型进行分类,分成start和end点。然后我们根据这些start和end节点的大小来排序,可以用Comparator接口,重写其compareTo方法。那么将节点新生成一个Point类。当碰到起点的时候,重叠个数加1,并且记录重叠个数的最大值;否则当遇到结束点时,重叠个数减1. 代码如下: class Inte
区间重叠的判断
判断区间 [x0, y0] 和区间 [x1,y1] 是否重叠,或者重叠部分区间是多少 如果要重叠部分是多少(前提是有重叠部分),重叠区间为 [max(x0, x1), min(y0, y1)] bool function(int x0,int y0,int x1,int y1){ return x0<y1 && x1<y0; }
算法爱好者——算法题:新的区间 ? 待解决
给出一个无重叠的按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。写一个函数实现这个功能。 格式: 输入行第一行输入一个待插入的区间,第二行输入原始区间列表,最后输出插入后形成的新的区间。 样例输入 [ 2,5 ] [ [ 1,2 ],[ 5,9 ] ] 样例输出 [ [ 1,9 ] ]
区间树查找区间算法的实现
区间树查找区间算法的实现,VC++实现,自动随机生成区间,查找最小区间和调度区间
算法<翻转链表的指定区间>
要求:翻转一个链表的指定区间,比如链表1->2->3->4->5,翻转第二个元素到第四个元素之后的新链表为:1->4->3->2->5思路:首先找到要翻转的第一个元素的前一个元素,比如现在我要翻转的区间是[2,4],那我首先要找到节点1。然后节点2置为翻转区间的头结点(在整个翻转过程中整个元素是不变的)。这里以翻转2、3节点为例子: 首先将节点1的next指针指向节点3,然后将节点2的next
有序区间求交集算法
题目描述:有两个有序的集合,集合的每个元素都是一段范围,求其交集,例如集合{[4,8],[9,13]}和{[6,12]}的交集为{[6,8],[9,12]}。 我们知道,两个集合的交集必定是去满足范围小的那个集合,因此此题的解法就是每次寻找一个小的范围。那么,关键之处就在于如何寻找这个范围。 如下图所示,两个集合{[2,8],[9,14]}和{[1,10],[12,15]}: 集合示例 ...
《算法笔记》4.4——区间贪心
题目:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两之间没有交集 例如:(1,3)、(2,4)、(3,5)、(6,7) 最多选3个:(1,3),(3,5)、(6,7) 贪心算法思想: 1、基础两点: a.优先选择短的区间 b.如果存在一个区间包含另一个区间,应选择更小的区间. 2、算法(左端点为例) 1、对区间左端点进行从大到小排序,左端点相同按右端点从小到大...
STL中的区间删除算法
STL中的区间删除算法 #include &quot;stdafx.h&quot; #include&amp;lt;iostream&amp;gt; #include&amp;lt;algorithm&amp;gt; #include&amp;lt;vector&amp;gt; #include&amp;lt;functional&amp;gt; #include&amp;lt;ctime&amp;gt; using namespace std; int main() { srand...
相关热词 c#部署端口监听项目、 c#接口中的属性使用方法 c# 昨天 c#func链接匿名方法 c#怎么创建文件夹 c#从键盘接收空格 c#da/ad c#部门请假管理系统 c#服务器socket c# 默认的访问修饰符