समय स्पैन के बीच ओवरलैप की जांच

Question

मेरे पास प्रारंभ समय और एक स्टॉप के साथ समय प्रविष्टियों (एचएचएमएम प्रारूप) की एक सूची है। मुझे पाइथन में कोड करने के तरीके को समझने में परेशानी हो रही है, जहां सूची में ओवरलैप है या नहीं, तो यह लौटाता है।

उदाहरण

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

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

Answer 1

सबसे पहले हम स्टार्ट टाइम द्वारा सूची को सॉर्ट करते हैं।

फिर हम इसे जांचते हुए लूप करते हैं कि अगला प्रारंभ समय पिछला अंत समय कम है या नहीं।

यह अगर x + 1 एक्स के साथ ओवरलैप हो जाँच करेगा (नहीं करता है, तो x + 2 एक्स के साथ, आदि overlaps)

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] 

निम्नलिखित पूरी सूची में आप सभी overlappings देना चाहिए।

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] 

ध्यान दें कि यह एक O (n * एन) देखने है। (अगर मैं गलत हूं तो कोई भी मुझे यहां सही करता है!)

यह संभवतः पहले की तुलना में धीमी है (इसका परीक्षण नहीं किया गया है, लेकिन मुझे लगता है कि यह है) क्योंकि यह प्रत्येक एकल अनुक्रमणिका के लिए पूरी सूची में पुनरावृत्त होता है। Loops उदाहरण के लिए arbarnert के घोंसला के समान होना चाहिए। लेकिन फिर यह आपको सभी ओवरलैपिंग मान देता है क्योंकि मैंने पहली विधि के विरोध में दिखाया है कि केवल इसके आगे के ओवरलैपिंग समय के लिए चेक किया गया है (प्रारंभ समय से क्रमबद्ध)।

विस्तारित परीक्षण देता है:

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

मान लें कि आप एक intervals_overlap(interval1, interval2) समारोह है ...

पहला विचार सूची में अंतराल की प्रत्येक जोड़ी पर एक अनुभवहीन यात्रा है:

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

लेकिन आप होना चाहिए इस डोंग के बेहतर तरीके से पता लगाने में सक्षम।

Answer 3

भविष्य में संदर्भ के लिए, @Roy के समाधान के अंतराल में एक ही अंत है या समय शुरू कि के लिए काम नहीं करता। निम्नलिखित समाधान करता है:

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]) 

इसके अलावा, एक Interval Tree समस्याओं के इन प्रकार के लिए इस्तेमाल किया जा सकता है।

Answer 4

सरल यह करने के लिए जिस तरह से:

मैं स्ट्रिंग में नंबर बदलने के बाद से प्रवेश 3 0900 में शामिल है, जो अवैध है।

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

@ रॉय की जवाब पर विस्तार करने के लिए स्थितियों में, जहां कुछ ही समय स्लॉट शामिल करने के लिए और आप को अलग करने की जरूरत है:

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']