如何在没有重叠间隔的情况下将间隔分类为最小数量的箱
How to sort intervals into minimum number of bins without overlapping intervals
我正在寻找一种算法来实现以下目标：
给定一组任意的“间隔”，其中间隔仅由开始和结束定义（2 个浮点数 end >= start）。我想将这些间隔组织成 1 个或多个“箱子”/“桶”/组，这样：
- 单个 bin 中没有两个区间相互重叠
- 已使用最小数量的 bin
我的解决方案是迭代间隔，并且对于每个间隔，基本上对每个 bin 执行二进制搜索，直到找到一个可以容纳间隔（如果需要，新 bin）。这行得通，但我想知道是否可以对其进行优化，因为根据处理间隔的顺序，结果会有所不同。我感觉将间隔从最大到最小排序 (end - start) 会得到更好的结果，但我不确定。
将区间按照端点排序，然后将每个区间按照端点顺序，放入最右边端点最大的桶中，使得bucket.max_endpoint < interval.startpoint.如果没有这个bucket，那么你就得重新开始一个。
如果您将存储桶保存在按 max_endpoint 排序的二叉搜索树中，那么您可以在 log(|buckets|) 时间内找到最佳存储桶，总共 O(N log N)。
为每个桶选择最紧密的拟合区间是最佳的证明很简单：
想象一下，您已经知道桶的最佳间隔分配，并且按照端点顺序将它们放入桶中，并且在某些时候您不选择最紧的-适合水桶...
如果您改变主意并选择最适合的桶，您将面临相同的情况，只是其中一个桶的空间 更多正确的。有更多空间永远不会有坏处，所以剩余的间隔仍然适合。
我正在寻找一种算法来实现以下目标：
给定一组任意的“间隔”，其中间隔仅由开始和结束定义（2 个浮点数 end >= start）。我想将这些间隔组织成 1 个或多个“箱子”/“桶”/组，这样：
- 单个 bin 中没有两个区间相互重叠
- 已使用最小数量的 bin
我的解决方案是迭代间隔，并且对于每个间隔，基本上对每个 bin 执行二进制搜索，直到找到一个可以容纳间隔（如果需要，新 bin）。这行得通，但我想知道是否可以对其进行优化，因为根据处理间隔的顺序，结果会有所不同。我感觉将间隔从最大到最小排序 (end - start) 会得到更好的结果，但我不确定。
将区间按照端点排序，然后将每个区间按照端点顺序，放入最右边端点最大的桶中，使得bucket.max_endpoint < interval.startpoint.如果没有这个bucket，那么你就得重新开始一个。
如果您将存储桶保存在按 max_endpoint 排序的二叉搜索树中，那么您可以在 log(|buckets|) 时间内找到最佳存储桶，总共 O(N log N)。
为每个桶选择最紧密的拟合区间是最佳的证明很简单：
想象一下，您已经知道桶的最佳间隔分配，并且按照端点顺序将它们放入桶中，并且在某些时候您不选择最紧的-适合水桶...
如果您改变主意并选择最适合的桶，您将面临相同的情况，只是其中一个桶的空间 更多正确的。有更多空间永远不会有坏处，所以剩余的间隔仍然适合。