Überschneidungsintervalle bestimmen

Question

Ich habe zwei Maschinen, und für jede Maschine habe ich die Intervalle, in denen sie arbeitete, als Liste der Startpunkte und Liste der Endpunkte der Intervalle (zum Beispiel [0, 5, 9]) und [3, 6, 13] würde anzeigen, dass die Maschine von 0 bis 3, 5 bis 6 und 9 bis 13 arbeitete.

Ich möchte bestimmen, wie die Start- und Endpunkte von Intervallen zu berechnen, wo genau eine Maschine arbeitete und genau zwei Maschinen waren die gleiche Zeit.

Wenn beispielsweise die Anfangs- und Endpunkte der zweiten Maschinenintervalle [0, 7] und [2, 10] waren, dann sind die Start- und Endpunkte der Intervalle, in denen genau eine Maschine arbeitete, [2, 5, 7 , 10] und [3, 6, 9, 13] und die Anfangs- und Endpunkte von Intervallen, wo genau zwei Maschinen arbeiteten, sind [0, 9] und [2, 10].

Ich möchte in der Lage sein, dies auf drei oder mehr Maschinen zu verallgemeinern. Diese

ist, was ich habe:

overlapping_interval_starts = {} 
overlapping_interval_ends = {} 
whole_list = [(start, 's') for start in interval_starts] + [(end, 'e') for end in interval_ends] 
whole_list.sort() 

count = 1 
if whole_list: 
    previous, _ = whole_list.pop(0) 
    for elt, elt_type in whole_list: 
     current = elt 
     if (count != 0) and (previous != current): 
      try: 
       overlapping_interval_starts[count].append(previous) 
       overlapping_interval_ends[count].append(current) 
      except KeyError: 
       overlapping_interval_starts[count] = [previous] 
       overlapping_interval_ends[count] = [current] 

     if elt_type == 's': 
      count += 1 
     else: 
      count -= 1 
     previous = current 

Es funktioniert am Beispiel Problem, das ich habe, aber ich bin nicht sicher, wie um zu überprüfen, es richtig, im Allgemeinen ist.

Zum Beispiel läuft es auf das folgende Problem:

Machine 1: [2, 7], [6, 11] 
Machine 2: [1, 5, 11], [3, 10, 13] 
Machine 3: [2, 6], [5, 8] 

ergibt:

overlapping_interval_starts = {1: [1, 10, 11], 
           2: [3, 5, 6, 8], 
           3: [2, 7]} 
overlapping_interval_ends = {1: [2, 11, 13], 
          2: [5, 6, 7, 10], 
          3: [3, 8]} 

die technisch korrekt, aber es sollte eigentlich nur zwei Intervalle sein (3 bis 7 und 8 bis 10) wo zwei Maschinen überlappen. Ich kämpfe darum, wie ich sicher sein kann, dass es im Allgemeinen funktioniert.

Answer 1

Schritt durch die gesamte Zeitleiste, beginnend mit dem ersten Zeitstempel. Mit anderen Worten ...

Ermitteln Sie die Mindeststartzeit aller verschiedenen Startzeitenlisten. Während des Intervalls, das zu diesem Zeitpunkt beginnt, gibt es eine Maschine, rufen Sie diese Maschine an.

Von den verbleibenden Startzeiten für alle anderen Computer außer M, und von den Endzeiten für M, finden Sie den minimalen Zeitstempel. Wenn es sich um eine Startzeit handelt, erhöhen Sie die Anzahl der Computer, die gleichzeitig arbeiten. Wenn es sich um eine Endzeit handelt, verringern Sie die Anzahl der Computer, die arbeiten.

Fahren Sie damit fort, bis Sie keine Zeitstempel mehr haben. Jedes Mal, wenn Sie eine Startzeit als Mindestzeit finden, wechseln Sie zu den Endzeiten des Computers. Jedes Mal, wenn Sie eine Endzeit als Mindestzeit finden, wechseln Sie zu Startzeiten des Computers.

Hier ist eine Visualisierung:

Computer A:  0-----3 5-6  9-------13 
Computer B:  0---2   7-----10 
       ^
Minimum stamp: 0 
Number working: 1 
As of time:  0 

################################################## 

Computer A:  X-----3 5-6  9-------13 
Computer B:  0---2   7-----10 
       ^
Minimum stamp: 0 
Number working: 2 
As of time:  0 

################################################## 

Computer A:  X-----3 5-6  9-------13 
Computer B:  X---2   7-----10 
        ^
Minimum stamp:  2 
Number working: 2 1 
As of time:  0 2 

################################################## 

Computer A:  X-----3 5-6  9-------13 
Computer B:  X---X   7-----10 
        ^
Minimum stamp:  3 
Number working: 2 1 0 
As of time:  0 2 3 

################################################## 

Computer A:  X-----X 5-6  9-------13 
Computer B:  X---X   7-----10 
         ^
Minimum stamp:   5 
Number working: 2 1 0 1 
As of time:  0 2 3 5 

################################################## 

Computer A:  X-----X X-6  9-------13 
Computer B:  X---X   7-----10 
          ^
Minimum stamp:    6 
Number working: 2 1 0 1 0 
As of time:  0 2 3 5 6 

################################################## 

Computer A:  X-----X X-X  9-------13 
Computer B:  X---X   7-----10 
          ^
Minimum stamp:    7 
Number working: 2 1 0 1 0 1 
As of time:  0 2 3 5 6 7 

################################################## 

Computer A:  X-----X X-X  9-------13 
Computer B:  X---X   X-----10 
           ^
Minimum stamp:     9 
Number working: 2 1 0 1 0 1 2 
As of time:  0 2 3 5 6 7 9 

################################################## 

Computer A:  X-----X X-X  X-------13 
Computer B:  X---X   X-----10 
            ^
Minimum stamp:      10 
Number working: 2 1 0 1 0 1 2 1 
As of time:  0 2 3 5 6 7 9 10 

################################################## 

Computer A:  X-----X X-X  X-------13 
Computer B:  X---X   X-----XX 
             ^
Minimum stamp:       13 
Number working: 2 1 0 1 0 1 2 1  0 
As of time:  0 2 3 5 6 7 9 10 13 

################################################## 

Computer A:  X-----X X-X  X-------XX 
Computer B:  X---X   X-----XX 
Minimum stamp:        Done 
Number working: 2 1 0 1 0 1 2 1  0 
As of time:  0 2 3 5 6 7 9 10 13