5

開始時刻と終了時刻を含む時間エントリ (HHMM 形式) のリストがあります。リストに重複があるかどうかにかかわらず、Pythonでコードを返す方法を理解するのに苦労しています。

エントリ 1: 1030、1245;
エントリ 2: 1115、1300
== 真

エントリ 1: 0900、1030;
エントリ 2: 1215、1400
== いいえ
4

5 に答える 5

11

まず、リストを開始時間で並べ替えます。

次に、次の開始時刻が前の終了時刻よりも短いかどうかを確認するためにループします。

これは、x+1 が x とオーバーラップしているかどうかをチェックします (x+2 が x とオーバーラップしているかどうかなどではありません)。

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]

以下は、リスト全体ですべての重複を与えるはずです。

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*n) ルックアップであることに注意してください。(私が間違っている場合は、ここで誰かが私を訂正してください!)

これは、単一のインデックスごとにリスト全体を反復処理するため、最初のものよりも遅い可能性があります (テストしていませんが、テストしていると思います)。arbarnert のネストされた for ループの例に似ているはずです。しかし、最初に示した方法では、隣の値の間の重複時間のみをチェックした (開始時間でソート) のとは対照的に、これはすべての重複値を提供します。

拡張テストでは次の結果が得られます。

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']
于 2013-02-14T22:44:08.400 に答える
2

今後の参考のために、@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])

また、インターバル ツリーは、この種の問題に使用できます。

于 2013-12-03T21:55:35.377 に答える
0

関数があると仮定するとintervals_overlap(interval1, interval2)…</p>

最初のアイデアは、リスト内の間隔のすべてのペアに対する単純な反復です。

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

しかし、これを回避するためのよりスマートな方法を見つけられるはずです。

于 2013-02-14T22:31:41.730 に答える
-1

それを行う簡単な方法:

エントリ 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
于 2014-11-30T06:33:36.610 に答える