CODEWITHSUNDEEP
algorithm
Robert Mugattarov
Robert Mugattarov

Reputation: 1298

Consecutively intersect two sets of intervals

We have two sets of intervals, A and B.

Every inteval in A is described by two positive real numbers {A1start,A1end},{A2start,A2end},...,{Anstart,Anend}. Anend is alsways > Anstart. Intervals in A MAY overlap.

The set B is only decribed by two values: interval length and interval distance. The interval length is the delta of every interval, i.e. Bnend - Bnstart, and is > 0. Interval distance is the distance between any two Bnstart. Intervals in B may NOT overlap.

We know that on any interval {A1start,Anend} the number of intervals in A and B SHOULD be equal.

The question is: on the interval of {A1start,Anend} can we intersect B with A consecutively? i.e. B1 must intersect A1, B2 must intersect A2 etc. It is fine if any B intersects any other A besides its designated one.

I have worked out two algorithm rules and currently stuck:

  1. B rules allow us to calculate the min and max number of intervals on any {A1start,Anend}, we use it to discard the cases when the number of intervals in A and B is unequal.
  2. If any gap in A is greater than B distance, we discard this case since at least one B won't intersect any A.

What other conditions must be true for these two sets to intersect consecutively?

Upvotes: 3

Views: 598

Answers (1)

samgak
samgak

Reputation: 24417

You can solve it like this:

  • Dilate all the intervals in A by the interval length of B by subtracting the length from all the Anstart values. You can think of A as now defining all the valid positions where an interval in B can start.
  • The problem is now whether you can intersect a series of points (B) spaced a given distance apart with a set of intervals (A). You can solve this by intersecting A1 with A2 offset by -distance, A3 offset by -2distance ... An offset by -(n-1)distance. If the intersection of all these intervals is non-empty then an intersection of A and B is possible.

Upvotes: 1

Related Questions