给定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
OUTPUT:
-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)