4
$\begingroup$

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time.

So each interval starts at a specific instant in time, 'occurs' for a duration of time, then repeats after a duration (period) of time.

Interval A

  • Start: 1s
  • End: 5s
  • Repeat Until: 50s

  • Repeat Period: 10s

      |-[xxx]-----[xxx]-----[xxx]-----[xxx]-----[xxx]----|

Interval B

  • Start: 7s
  • End: 10s
  • Repeat Until: 50s

  • Repeat period: 9s

      |-------[xx]-----[xx]-----[xx]-----[xx]-----[xx]---|

Timeline

A:|-[xxx]-----[xxx]-----[xxx]-----[xxx]-----[xxx]----|
B:|-------[xx]-----[xx]-----[xx]-----[xx]-----[xx]---|

If these were considered linear (which they are partially - except for the duration) I could just set two equations equal to each other to figure out when they conflict.

|-x---x---x---x---x---x---x---x---x---x---x---x---x|

event.start + event.period(num of repeats) = new event.start
other.start + other.period(num of repeats) = new other.start

Set equal to each other solve for num of repeats

However I'm only dealing with integers, I'm checking for overlap not an exact point in time, and it doesn't tell me when other intervals overlap. I'm lost.

Representing these intervals so that I can calculate when they overlap and for how long is really the bottom line. I'm missing an important concept here that I can't quite get, some thoughts included series, regression, and brute force (calculate every position manually) but I'm lost without a clear understanding of math to help me forward.

$\endgroup$
6
  • $\begingroup$ Ar eyou only interested in cases of two intervals at a time? Or do you need an algorithm that is efficient for detecting collisions between many intervals, or many pairs of intervals? And are the numbers in your examples typical? Or are the numbers in your actual application much larger? $\endgroup$
    – MJD
    Nov 28, 2013 at 15:18
  • $\begingroup$ Thanks for the edits - There are multiple intervals, I could potentially compare pairs. And no the numbers are as you said much bigger but I'm not sure that makes a difference (I could apply by units instead - years, months, days, hours, minutes, seconds, miliseconds) Time gets really confusing... $\endgroup$
    – Nate-Wilkins
    Nov 28, 2013 at 15:28
  • $\begingroup$ And I'm not sure what you want the output of your algorithm to be. Is it just a true or false value that indicates whether the input intervals overlap? Or is it some sort of description of when the overlaps occur? And if the latter, does the description have to be another interval in the same format? Or could it be some other sort of structure? (You might answer this by editing your question instead of trying to squeeze the answer into a comment.) $\endgroup$
    – MJD
    Nov 28, 2013 at 15:30
  • $\begingroup$ Also I find your diagram confusing. It seems to me that structure $A$ indicates that something is active for 4 seconds out of every 10, but the diagram shows either 3 or 5 boxes checked. I think $A$ means that some even occurs from $t=1$ until $t=5$, from $t=11$ until $t=15$, and then similarly from $21$ until $25$, from $31$ until $35$, from $41$ until $45$, and then never occurs again. Is that correct? $\endgroup$
    – MJD
    Nov 28, 2013 at 15:33
  • $\begingroup$ The latter - 'description' when the next overlap starts/ends $\endgroup$
    – Nate-Wilkins
    Nov 28, 2013 at 15:45

2 Answers 2

Reset to default
1
+50
$\begingroup$

You would like to know which integers satisfy two conditions:

  • $t \equiv 1,2,3,4,5\; (\,mod \,10\,)$
  • $t \equiv 7,8,9,10\; (\,mod \,9\,)$

Since you're a programmer you may want to think of this as

  • t % 10 in [1,2,3,4,5]
  • t % 9 in [0,1,7,8]

Since 9 and 10 are relatively prime, we can always find numbers which satisfy congruence conditions mod 9 and mod 10 by the Chinese Remainder Theorem.

Let's focus on solving the equation $ t \equiv a\; \text{mod}\;m$ and $ t \equiv b\; \text{mod}\;n$ with $m,n$ relatively prime. In fact, $10-9=1$ so we are good.

Using the Euclidean algorithm, we can efficiently find two numbers two numbers $a_0, b_0 \in \mathbb{Z}$ such that $ma_0 + nb_0 = 1$. This means $$ b_0 n \equiv 1\; \text{mod}\;m \hspace{0.25in}\text{&}\hspace{0.25in}a_0 m \equiv 1\; \text{mod}\;n$$

So $t = ab_0 n + a_0 b m$ satisfies both congruences.

In our case, $10-9=1$ so that $1(-9)+3(10)= 21 $ satisfies $21\equiv 1 \; \text{mod}\;10$ and $21\equiv 3 \; \text{mod}\;9$. Since your intervals are of length 4 and 5, there are 20 possible overlap times you have to watch out for.

$\endgroup$
5
  • $\begingroup$ I think your on the right track but not sure where '[0, 1, 7, 8]' came from... or what the diagrams mean? Thanks for the help! $\endgroup$
    – Nate-Wilkins
    Nov 24, 2013 at 17:35
  • $\begingroup$ The other questions this imposes is when and where... I don't necessarily want to run through all times t from 0 to upper bound (if there even is one) $\endgroup$
    – Nate-Wilkins
    Nov 24, 2013 at 20:14
  • 1
    $\begingroup$ that is an interesting question. how do we "efficiently" find solutions to M different congruence conditions? $\endgroup$
    – cactus314
    Nov 25, 2013 at 11:49
  • $\begingroup$ Indeed I really don't want to be 'guess checking' :) $\endgroup$
    – Nate-Wilkins
    Nov 26, 2013 at 20:54
  • $\begingroup$ I'm going to look into this a little more before I accept but you deserve the bounty! $\endgroup$
    – Nate-Wilkins
    Nov 29, 2013 at 23:15
0
$\begingroup$

I could not think of a definite answer but this approach might help...

Code the two sequences in binary with the intervals being '+1' and repetition periods being '0's. Get the dot product of the two binary sequences. The number of '1's will give you the total duration of overlap. Also the number of overlaps can be obtained by counting the number of uninterrupted sequences of '1's

If the repeat until duration of one signal is smaller than the other pad the smaller one with zeros at the end.

Hope you get the idea.

$\endgroup$
1
  • $\begingroup$ I thought of something very similar but without bit masks I'm just afraid that my domain set becomes too large... $\endgroup$
    – Nate-Wilkins
    Nov 29, 2013 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.