几周前有人在这里发布了这个问题，但它看起来非常像没有事先研究的家庭作业，并且 OP 在得到一些反对意见后立即将其删除。
不过，这个问题本身相当有趣，我已经考虑了一周，但没有找到令人满意的解决方案。希望有人可以提供帮助？
问题如下：给定一个包含 N 个整数区间的列表，其边界可以从0到取任意值，找到不属于任何输入区间N³的最小整数。ii
例如，如果给定列表[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³bound有关，但我不确定是什么......散列？线性时间排序？欢迎提出想法。
这是上述算法的粗略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