给定一组对象，每个对象都放在自然数线上的几个位置:找到包含所有对象的最小区间 [a, b]。
示例:考虑 3 个对象 A、B、C
A 位于 1, 5, 7
B 位于 2, 4, 6
C 放在 4, 8, 9
包含所有三个对象的最小区间是[4, 5]。
我只能想到 O(S^2) 解决方案，其中 S 是包含所有对象位置的最小间隔，即 [1, 9] 。
有更好的方法吗？
PS:请注意，多个对象可以放置在同一位置。
最佳答案
将所有数据点按升序排序(nlogn次)。
从左边开始遍历这些数据点。
跟踪以下内容:
1. 对于每种类型的对象，维护找到的最后一个对象的坐标条目(为了快速操作，可能通过 hashmap)。
2. 目前找到的最小区间长度
3. 列表中最早元素的坐标。这是为了跟踪当前间隔的开始。
每当你遇到一个物体，
1. 更新其在维护列表中的条目。
2. 查看最早元素坐标是否更新。如果是，则计算新的间隔长度，如果新的间隔长度更小，则更新最小间隔长度。
您首先需要确定您遇到了所有类型的对象，以计算第一个有效的最小间隔长度。您可以通过柜台办理。
如果不同类型元素的数量是有界的并且很小，那么复杂度的阶数是 O(nlogn)，其中 n 是数据点的总数。
关于algorithm - 包含所有对象的最小区间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20310056/