给定一个源区间[x,y](y>=x)和N个无序的目标区间[x1,y1][x2,y2]......[xn,yn],判断区间[x,y]在不在目标区间内。
/**
*区间覆盖问题
*输入:n个区间,有可能重合,还有一个区间,判断这个区间是不是与这n个区间完全重合
*输出:true or false
*步骤:先将n个区间按start进行排序O(nlogn),然后根据这些区间的start和end将这些区间合并成为 *互相不相交的区间O(n),然后判断给定区间是否与这些不相交的区间完全重叠
*/
import java.util.*;
class Interval{
int start;
int end;
public Interval(int start, int end){
this.start = start;
this.end = end;
}
}
public class IntervalOverlap{
public static void main(String[] args){
List intervalList = new ArrayList();
Interval i1 = new Interval(2,3);
Interval i2 = new Interval(1,2);
Interval i3 = new Interval(3,9);
intervalList.add(i1);
intervalList.add(i2);
intervalList.add(i3);
Interval i4 = new Interval(1,6);
System.out.println(whetherOverlap(intervalList,i4));
}
private static boolean whetherOverlap(List intervalList, Interval i){
Comparator intervalComparator = new Comparator(){
public int compare(Object o1, Object o2){
Interval i1 = (Interval)o1;
Interval i2 = (Interval)o2;
return i1.start-i2.start;
}
};
Collections.sort(intervalList, intervalComparator);
for(int j=0;j<intervalList.size()-1;j++){
Interval i1 = (Interval)intervalList.get(j);
Interval i2 = (Interval)intervalList.get(j+1);
if(i1.end>=i2.start){
i1.end = i2.end;
intervalList.remove(j+1);
j--;
}
}
for(int j=0;j<intervalList.size();j++){
Interval interval = (Interval)intervalList.get(j);
if(interval.start<=i.start && interval.end >= i.end)
return true;
}
return false;
}
}
分享到:
相关推荐
实现4-10区间覆盖问题.cpp
情形1:区间完全覆盖问题 情形2:最大不相交区间数问题 情形3:区间选点问题
区间覆盖的代码,算法书上的一些杂糅以及自己的想法,上传凑个积分用,如有雷同算我抄你!
区间覆盖的源代码和原始输入数据 希望下载后加一个评论
1288. 删除被覆盖区间典型的区间覆盖问题# 1. 找到覆盖区间# 2. 找到相交区间,合并# 3. 完全不想交,更新起始点return len(interv
分治法不仅可以用来设计算法,而且还在循环赛日程表中有应用。
区间覆盖最大leetcode 数据结构和算法 具有全面测试、覆盖和跨平台持续集成的数据结构和算法。 这个存储库的目标是从一个问题平稳地过渡到另一个问题,记录有趣的方面,并涵盖大量实际问题。 数据结构 堆 队列 链表 ...
给定n个整数 组成的序列。如果对于 ,有 ,则称 覆盖序列区间 ,相应的覆盖区间长度为j-i+1。 最大覆盖问题要求给定序列的最大覆盖区间长度L,即:
- 区间覆盖问题 & - 区间选点问题 & - 流水作业调度问题 & - 带期限和罚款的单位时间任务调度问题 五大贪心问题模板与解析。 适合人群: 普及晚期或提高早期的萌新 OIer 们。 (参考并整合自《信息学奥赛...
给定N个整数 A1,A2....AN组成序列。如果对于i,有Ak|Aj|,则称Aj覆盖序列区间Ai....Aj,相应的覆盖区间长度为j-i+1。最大覆盖问题就是求给定序列的最大覆盖区间长度!
该word文档包含贪心算法的思想,适用于用贪心算法解决的问题的特性,贪心算法解题步骤,经典实例(钱币找零问题、活动选择问题、区间覆盖问题、小船过河问题、Dijkstra最短路径算法(图)、prim最小生成树算法、...
文件中有一份是 题目,另一份是已测试通过的代码
给定N个整数 组成的序列.A1,A2,....,An 如果对于i 则有Ak ¦Aj ¦ 称Aj覆盖序列区间Ai,Ai+1,...,Aj 覆盖区间长度为j-i+1 求最大覆盖区间长度 算法设计要求0(N) 例:序列1,6,2,1,-2,3,5,2,-4,3时 L=5
给定n个整数a1,a2,…,an组成的序列。 如果对于i≤k ≤j,有ak ≤|aj|,则称aj覆盖序列区间ai,ai+1,…,aj。 相应的覆盖区间长度为j-i+1。 本题要求计算给定序列的最大覆盖区间长度。
三类基于贪心算法覆盖问题先按b从小到大进行排序,再选择b0作为选点pos,以每个村庄坐标为圆心,D为半径画圆,与X轴有两个交点,得到一个区间,得到N个区间后,就转化为了
针对覆盖粗糙集仅适用于单一数据...该模型适用于多种数据类型(符号数据、区间数据、集合数据、数值数据等)的论域覆盖问题,通过实例说明了该模型在复合信息系统中的应用,进一步加深对复合覆盖粗糙集相关概念的理解。
3 最小路径覆盖问题 有向无环图最小路径覆盖 网络最大流 4 魔术球问题 有向无环图最小路径覆盖 网络最大流 5 圆桌问题 二分图多重匹配 网络最大流 6 最长递增子序列问题 最多不相交路径 网络最大流 7 试题库问题 ...
### 团队长期从事下列领域算法的研究和改进: ### 1 智能优化算法及应用 ...##### 6.2 无线传感器覆盖优化 ##### 6.3 无线传感器通信及优化(Leach协议优化) ##### 6.4 无人机通信中继优化(组播优化)
贪心算法的一些经典问题 1。独立区间问题 ...给一个大区间,再给出N个小区间,求出最少用多少个区间可以把大区间覆盖完 先选出开始的一个,然后选开始点在这个区间里结束点最大的区间,然后以次类推
介绍广州地铁线路建设过程中无线集群通信系统的覆盖方式,重点分析在隧道区间面对车载 电台与手持电台信号覆盖的取含问题、直放站的同频干扰问题,并分析地铁无线集群覆盖建设的发 展趋势。