几周前，有人在这里发布了这个问题，但看起来像是没有先前研究的作业，OP在得到一些负面评价后立即将其删除。
尽管如此，这个问题本身相当有趣，我已经思考了一个星期，却没有找到令人满意的解决方法。希望能有人帮忙吗？
问题如下：给定N个整数区间的列表，其边界可以取任何值从0到N³，找到不属于任何输入区间的最小整数i。
例如，如果给定列表[3,5] [2,8] [0,3] [10,13](当N=4)，则该算法应返回9。
我可以想到的最简单的解决方案运行时间为O(n log(n))，并由三个步骤组成：
- 按增加的下限对间隔进行排序
- 如果最小下限>0，则返回0;
- 否则重复合并第一个间隔与第二个间隔，直到第一个间隔(比如
[a,b])不与第二个间隔(比如[c,d])接触——也就是说，直到b+1<c，或只剩一个间隔。
- 返回
b + 1
这个简单的解决方案运行时间为O(n log(n))，但原始发布者写道该算法应该在O(n)中运行。如果间隔已排序，那就很容易了，但OP给出的例子包括未排序的间隔。 我猜这可能与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
其边界可以取0到N³的任何值（应为1而非0）。 - Vincent