Algorithme pour trouver si les intervalles de temps régulièrement récurrents se chevauchent?

Question

Il existe plusieurs intervalles de temps récurrents, commençant à partir de startTime jusqu'à endTime. Chaque intervalle est défini par l'heure de début de la récurrence, l'heure de fin (jusqu'au point où la récurrence va se poursuivre), l'onDuration (quand elle est active et peut se chevaucher), et la durée d'extinction.

Intervalle d'échantillonnage:

startTime: 3 secs 
endTime: 30 secs 
onDuration: 3 secs (represented by x) 
offDuration: 5 secs (represented by -) 

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

Chevauchement Intervalles: Deux séries récurrentes sont dites à se chevaucher si elles ont chevauchement en temps (x) à l'intérieur de début et de plages de temps de fin de chacun d'eux.

Question: Il existe des dizaines de tels intervalles. Un nouvel intervalle récurrent, défini par les mêmes paramètres (startTime, endTime, onDuration, offDuration) est fourni. Ce nouvel intervalle récurrent chevauche-t-il l'un des intervalles existants, dans les plages horaires de startTime et endTime?

PotentialInterval:

startTime: 6 secs 
endTime: 15 secs 
onDuration: 3 secs 
offDuration: 6 secs 

PotentialInterval ne pas en conflit avec SampleInterval parce qu'elle se termine avant qu'il aurait chevauché.

Remarques:

1. Ceci est très similaire à this question, mais je ne pouvais pas comprendre complètement l'exactitude de la solution. De plus, je ne cherche qu'à déterminer s'ils sont en conflit (booléen vrai ou faux), plutôt que l'intervalle conflictuel réel.

2. L'heure de fin et l'heure de début de chaque intervalle forment une progression arithmétique. startTime _n = startTime + (n-1) (onDuration + offDuration) où startTime _n < endTime. Ainsi, peut-être this question pourrait pointer dans la bonne direction, même si je ne pouvais pas trouver un moyen d'incorporer des durées dans ce domaine.

3. Les échantillons sont beaucoup plus petits. En réalité, le nombre d'intervalles individuels dans chaque récurrence serait de plusieurs milliers (par exemple, d'ici à 10 ans tous les jours de 15h à 16h). En outre, le nombre de récurrences pourrait être des centaines. Ainsi, dénormaliser les données (faire une liste de chaque occurrence) peut ne pas être pratique.

4. Ces données sont stockées dans une base de données NoSQL, donc des manipulations de date-heure dans la base de données ne sont pas possibles. Cela doit être fait en mémoire, et de préférence dans l'ordre de ~ 500 millisecondes

Answer 1

Je ne pense pas qu'il y ait une formule simple/algorithme pour déterminer si deux séries se chevauchent. Je vais élaborer un peu. Soit s1 = startTime de la série 1, a1 = onDuration, b1 = offDuration, e1 = endTime et c1 = a1 + b1. Soit également s2, a2, b2, c2 et e2 de la même façon pour series2. La question est, est-ce que les périodes sur les séries se chevauchent? Soit i1 une période particulière de la série 1, i1> = 0, i1 < = floor ((e1-k1)/c1) = m1. (J'ignore les queues droites de la série, mais celles-ci peuvent être traitées séparément.De même pour i2. La question est alors de savoir si on peut trouver les entiers i1 et i2 tels que les intervalles [s1 + i1 * c1, s1 + i1 * c1 + a1] et [s2 + i2 * c2, s2 + i2 * c2 + a2 ] chevauchement? Comme M69 suggère, ce qui équivaut à vérifier si

abs((s1+2*i1*c1+a1)/2 - (s2+2*i2*c2+a2)/2) < (a1+a2)/2 

Nous avons deux possibilités, soit l'expression sous le module est positif ou il est négatif. Supposons que ce soit positif, nous avons

0 <= i1 <= m1 
0 <= i2 <= m2 
s1+2*i1*c1+a1 >= s2+2*i2*c2+a2, 
s1+2*i1*c1+a1 - (s2+2*i2*c2+a2) < a1 + a2 

Ou,

0 <= i1 <= m1 
0 <= i2 <= m2 
i1 >= c2/c1*i2 + (s2-s1+a2-a1)/(2*c1) 
i1 < c2/c1*i2 + (2*a2+s2-s1)/(2*c1) 

(Si tout va bien, je n'ai pas fait des erreurs stupides en algèbre). Nous obtenons un autre système en supposant que l'expression sous le module est négative.

Ceci est un polygone éventuellement non vide avec au plus six côtés. La question est, est-ce que des valeurs entières tombent à l'intérieur? C'est un problème d'inégalités linéaires diophantiennes. Si vous google, vous revenez à un site soeur :)

https://mathoverflow.net/questions/69966/algorithm-for-solving-systems-of-linear-diophantine-inequalities