Controllo della sovrapposizione tra gli intervalli di tempo

Question

Ho un elenco di voci temporali (formato HHMM) con un'ora di inizio e una fermata. Sto avendo problemi a capire come codificarlo in Python dove ritorna se c'è una sovrapposizione o meno nella lista.

Esempio

 
Entry 1: 1030, 1245; 
Entry 2: 1115, 1300 
== True 

Entry 1: 0900, 1030; 
Entry 2: 1215, 1400 
== False 

Answer 1

Per prima cosa ordiniamo l'elenco per ora di inizio.

Quindi eseguiamo un ciclo su di esso controllando se la prossima ora di inizio è inferiore all'ora di fine precedente.

Questo controllerà se x + 1 si sovrappone con x (non se x + 2 si sovrappone con x, ecc)

intervals = [[100,200],[150,250],[300,400]] 
intervalsSorted = sorted(intervals, key=lambda x: x[0]) # sort by start time 
for x in range(1,len(intervalsSorted)): 
    if intervalsSorted[x-1][1] > intervalsSorted[x][0]: 
     print "{0} overlaps with {1}".format(intervals[x-1], intervals[x]) 

# result: [100, 200] overlaps with [150, 250] 

Il seguente dovrebbe darvi tutte le sovrapposizioni in tutta la lista.

intervals = [[100,200],[150,250],[300,400],[250,500]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 

# results: 
# [100, 200] overlaps with [150, 250] 
# [250, 500] overlaps with [300, 400] 

Si noti che questa è una ricerca O (n * n). (chiunque mi corregga qui se ho torto!)

Questo è probabilmente più lento del primo (non lo test, ma presumo che lo sia) perché questo itera su tutta la lista per ogni singolo indice. Dovrebbe essere simile all'esempio nested for loop di arbarnert. Ma poi di nuovo questo ti dà tutti i valori sovrapposti rispetto al primo metodo che ho mostrato che controllava solo i tempi di sovrapposizione tra quelli adiacenti (ordinati per ora di inizio).

test esteso dà:

intervals = [[100,200],[150,250],[300,400],[250,500],[10,900],[1000,12300],[-151,32131],["a","c"],["b","d"],["foo","kung"]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] ] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 

# results: 
# [100, 200] overlaps with [150, 250] 
# [250, 500] overlaps with [300, 400] 
# [10, 900] overlaps with [100, 200] 
# [10, 900] overlaps with [150, 250] 
# [10, 900] overlaps with [300, 400] 
# [10, 900] overlaps with [250, 500] 
# [-151, 32131] overlaps with [100, 200] 
# [-151, 32131] overlaps with [150, 250] 
# [-151, 32131] overlaps with [300, 400] 
# [-151, 32131] overlaps with [250, 500] 
# [-151, 32131] overlaps with [10, 900] 
# [-151, 32131] overlaps with [1000, 12300] 
# ['a', 'c'] overlaps with ['b', 'd'] 

Answer 2

a patto di avere una funzione intervals_overlap(interval1, interval2) ...

La prima idea è un'iterazione ingenuo su ogni coppia di intervalli nella lista:

for interval1 in intervals: 
    for interval2 in intervals: 
     if interval1 is not interval2: 
      if intervals_overlap(interval1, interval2): 
       return True 
return False 

Ma si dovrebbe essere in grado di capire modi più intelligenti di dong questo.

Answer 3

Per riferimento futuro, la soluzione di @Roy non funziona per gli intervalli che hanno lo stesso fine o orari di inizio. La seguente soluzione fa:

intervals = [[100, 200], [150, 250], [300, 400], [250, 500], [100, 150], [175, 250]] 
intervals.sort() 
l = len(intervals) 
overlaps = [] 
for i in xrange(l): 
    for j in xrange(i+1, l): 
    x = intervals[i] 
    y = intervals[j] 
    if x[0] == y[0]: 
     overlaps.append([x, y]) 
    elif x[1] == y[1]: 
     overlaps.append([x, y]) 
    elif (x[1]>y[0] and x[0]<y[0]): 
     overlaps.append([x, y]) 

Inoltre, un Interval Tree potrebbero essere utilizzati per questi tipi di problemi.

Answer 4

modo semplice per farlo:

cambio il numero nella stringa dopo l'ingresso 3 contiene 0900, che non è valido.

entry01 = ('1030', '1245') 
entry02 = ('1115', '1300') 

entry03 = ('0900', '1030') 
entry04 = ('1215', '1400') 

def check(entry01, entry02): 
    import itertools 
    input_time_series = list(itertools.chain.from_iterable([entry01, entry02])) 
    if input_time_series != sorted(input_time_series): 
     return False 
    return True 

>>> check(entry01, entry02) 
False 
>>> check(entry03, entry04) 
True 

Answer 5

Ad ampliare @ risposta di Roy per includere situazioni in cui qualcosa è la stessa fascia oraria ed è necessario distinguere:

intervals = [[100,200, "math"],[100,200, "calc"], [150,250, "eng"],[300,400, "design"],[250,500, "lit"],[10,900, "english"],[1000,12300, "prog"],[-151,32131, "hist"]] 

overlapping = [ [x,y] for x in intervals for y in intervals if x is not y and x[1]>y[0] and x[0]<y[0] or x[0]==y[0] and x[1]==y[1] and x is not y] 
for x in overlapping: 
    print '{0} overlaps with {1}'.format(x[0],x[1]) 


# Prints 
#[100, 200, 'math'] overlaps with [100, 200, 'calc'] 
#[100, 200, 'math'] overlaps with [150, 250, 'eng'] 
#[100, 200, 'calc'] overlaps with [100, 200, 'math'] 
#[100, 200, 'calc'] overlaps with [150, 250, 'eng'] 
#[250, 500, 'lit'] overlaps with [300, 400, 'design'] 
#[10, 900, 'english'] overlaps with [100, 200, 'math'] 
#[10, 900, 'english'] overlaps with [100, 200, 'calc'] 
#[10, 900, 'english'] overlaps with [150, 250, 'eng'] 
#[10, 900, 'english'] overlaps with [300, 400, 'design'] 
#[10, 900, 'english'] overlaps with [250, 500, 'lit'] 
#[-151, 32131, 'hist'] overlaps with [100, 200, 'math'] 
#[-151, 32131, 'hist'] overlaps with [100, 200, 'calc'] 
#[-151, 32131, 'hist'] overlaps with [150, 250, 'eng'] 
#[-151, 32131, 'hist'] overlaps with [300, 400, 'design'] 
#[-151, 32131, 'hist'] overlaps with [250, 500, 'lit'] 
#[-151, 32131, 'hist'] overlaps with [10, 900, 'english'] 
#[-151, 32131, 'hist'] overlaps with [1000, 12300, 'prog']