java - 结合 2 个区间
问题描述
给定 2 个具有 int start、int end 和 boolean 状态的区间,组合 2 个区间,如下所示,
i1 和 i2 为 2 ArrayList<Intreval>
,并且 res 应包含组合区间的输出。
例子:
-INF --------- 6 ------- 10 --------- 30 --------- INF
F T T F
-INF --- 5 ------------------- 20 --------- 35 ---- INF
T T F F
输出:
-INF ---5 ---- 6 -------- 10 -- 20 ---- 30 -- 35 --- INF
F F T T F F F
该代码创建 i1 和 i2 ,它们是ArrayList<Intervals>
.
i1 has [[-INF,6,false],[6,10,true],[10,30,true],[30,INF,false]]
并且
i2 has [[-INF,5,true],[5,20,true],[20,35,false],[35,INF,false]]
和res should contain [[-INF,5,false],[5,6,false],[6,10,true],[10,20,true],[20,30,false],[30,35,false],[35,INF,false]]
代码:
Class Interval
{
int start;
int end;
boolean status;
public Interval(int start, int end, boolean status)
{
this.start = start;
this.end = end;
this.status = status;
}
}
class MyCode {
public static void main (String[] args) {
ArrayList<Interval> i1 = new ArrayList<Interval>();
i1.add(new Interval(Integer.MIN_VALUE, 6, false));
i1.add(new Interval(6,10,true));
i1.add(new Interval(10,30,true));
i1.add(new Interval(30,Integer.MAX_VALUE,false));
ArrayList<Interval> i2 = new ArrayList<Interval>();
i2.add(new Interval(Integer.MIN_VALUE, 5, true));
i2.add(new Interval(5,20,true));
i2.add(new Interval(20,35,false));
i2.add(new Interval(35,Integer.MAX_VALUE,false));
int i=0, j=0;
ArrayList<Interval> res = new ArrayList<Interval>();
}
}
解决方案
间隔覆盖所有轴,因此我们可以只考虑左端和 T/F 字段。
结束已排序,因此应用合并过程(如合并排序中的一个)。
ia = 0
ib = 0
//Start the first output interval code
while ia < ACount and B < BCount
if A[ia].Position <= B[ib].Position
ia++
AActive = True
else if A[ia].Value >= B[ib].Value //reuse == case for simplicity
// and incrementing both indexes
ib++
AActive = False
State = A[ia].BooleanField && B[ib].BooleanField
Pos = A[ia].Position if AActive else B[ib].Position
CloseOutputInterval(Pos)
StartOutputInterval(Pos, State)
continue with the rest (A or B left)
推荐阅读
- apache-spark - 在不使用 UDF 的情况下基于映射转换 Spark DataFrame 中的列
- sql - 将 SQL Server 2017 报告服务添加到 SQL 群集
- sql - 每行的列中的 SQL 总和值
- javascript - 使用 s3 上传图像时“缺少请求的请求令牌”
- git - 什么是 git 中的 original/refs/remotes/... 分支
- python - 使用 Python 的 IsoDep 卡
- json - OPENJSON 中的动态枢轴
- python - Pyarrow 不适用于 Python 3.8 ModuleNotFoundError AttributeError
- python - Python 会话 SAMESITE=None 未设置
- hyperledger-fabric - 配置双头 CA