Combining 2 Intervals

问题: Given 2 Intervals with int start, int end and boolean status, Combine the 2 Intervals as shown below i1 and i2 are 2 ArrayList<Intreval> and res should contain the o...

问题:

Given 2 Intervals with int start, int end and boolean status, Combine the 2 Intervals as shown below

i1 and i2 are 2 ArrayList<Intreval> and res should contain the output of the combined intervals.

Example:

-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

The code creates i1 and i2 which are ArrayList<Intervals>.
i1 has [[-INF,6,false],[6,10,true],[10,30,true],[30,INF,false]] and
i2 has [[-INF,5,true],[5,20,true],[20,35,false],[35,INF,false]] and
res should contain [[-INF,5,false],[5,6,false],[6,10,true],[10,20,true],[20,30,false],[30,35,false],[35,INF,false]]

Code:

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>();
    }
}

回答1:

Intervals cover all the axis, so we can consider only left ends together with T/F field.

Ends are sorted, so apply merging procedure (like one from merge sorting).

 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)
  • 发表于 2019-03-08 08:07
  • 阅读 ( 179 )
  • 分类:sof

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除