algorithm - 区间分组的高效算法

Question

我需要找到解决以下问题的算法:

给定一个间隔列表(leftBound，RightBound)，这是对这种行为中的间隔进行分组的最有效算法:

间隔:(1,4),(6,9),(1,3),(4,8),(6,9),(2,7),(10,15)

想要的解决方案:

组 (2,3) 包含 (1,3), (1,4), (2,7)

组 (6,8) 包含 (4,8), (6,9)

组 (10,15) 包含 (10,15)

当然有不同的可能解决方案:(2,7) 也可以在第二组中。

我的方法是按左边界升序对间隔进行排序，如果它们具有相同的左边界，则按右边界降序。然后我只是循环排序的间隔并尝试将它们添加到我之前构建的组中。如果这不可能，我会为此间隔建立一个新组并继续循环处理剩余的订单。

此算法是否保证我在我的时间间隔内收到尽可能少的不同组？你能说这是解决这个问题的贪婪方法吗？

Answer 1

这里有一个建议:

1. 按右边界排序:(1,3), (1,4), (2,7), (4,8), (6,9), (6,9), (10,15) .

2. 创建具有最低条目(rightBound - 1，rightBound)的组并将其删除:(2,3): (1,3) .

3. 将所有可能的间隔添加到组中并删除它们:(2,3): (1,3), (1,4), (2,7) .

4. 重复 2. 和 3. 直到列表为空:1. (2,3): (1,3), (1,4), (2,7); 2. (7,8): (4,8), (6,9), (6,9); 3. (14,15): (10, 15) .

5. 可选:将组扩大到最大大小或使用最低条目作为组间隔 (2.) 并在添加间隔时增加左边界 (3.)。

我认为它应该提供最少数量的组，因为在第 2 步中，我们创建了一个无法避免的组，然后在第 3 步中，我们添加了我们可以添加的所有内容。