誰かがこの質問を数週間前にここに投稿しましたが、事前の調査なしでは宿題のように見え、OP はいくつかの反対票を受け取った後、すぐに削除しました。
質問自体はかなり興味深いものでしたが、満足のいく解決策が見つからないまま、1 週間考え続けました。うまくいけば、誰かが助けることができますか？
問題は次のとおりです。範囲が からまでの任意の値を取ることができる N 個の整数区間のリストが与えられた場合、どの入力区間にも属さないような最小の整数を見つけます。0N³ii
たとえば、リスト[3,5] [2,8] [0,3] [10,13](N = 4) が与えられた場合、アルゴリズムは を返す必要があり9ます。
私が考えることができる最も簡単な解決策は で実行さO(n log(n))れ、3 つのステップで構成されます。
- 下限を増やして間隔を並べ替える
- 最小の下限が > 0 の場合は 0 を返します。
[a, b]それ以外の場合は、最初の間隔 (たとえば) が 2 番目の間隔 (たとえば ) に触れなく[c, d]なるまで、つまり、b + 1 < c になるまで、または間隔が 1 つになるまで、最初の間隔と 2 番目の間隔を繰り返しマージします。
- 戻る
b + 1
この単純なソリューションは で実行されますO(n log(n))が、元の投稿者は、アルゴリズムは で実行する必要があると書いていますO(n)。間隔が既にソートされている場合、それは簡単ですが、OP が示した例にはソートされていない間隔が含まれていました。boundと何か関係があるに違いないと思いますが、何がわからN³ないのですか...ハッシュ？線形時間ソート？アイデアは大歓迎です。
上記のアルゴリズムの大まかな python 実装を次に示します。
def merge(first, second):
(a, b), (c, d) = first, second
if c <= b + 1:
return (a, max(b, d))
else:
return False
def smallest_available_integer(intervals):
# Sort in reverse order so that push/pop operations are fast
intervals.sort(reverse = True)
if (intervals == [] or intervals[-1][0] > 0):
return 0
while len(intervals) > 1:
first = intervals.pop()
second = intervals.pop()
merged = merge(first, second)
if merged:
print("Merged", first, "with", second, " -> ", merged)
intervals.append(merged)
else:
print(first, "cannot be merged with", second)
return first[1] + 1
print(smallest_available_integer([(3,5), (2,8), (0,3), (10,13)]))
出力：
Merged (0, 3) with (2, 8) -> (0, 8)
Merged (0, 8) with (3, 5) -> (0, 8)
(0, 8) cannot be merged with (10, 13)
9