有效的区间分组算法

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,3），（1,4），（2,7），（4,8），（6,9），（6,9），（10,15）。

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

将所有可能的间隔添加到组中并删除它们：（2,3）：（1,3），（1,4），（2,7）。

重复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） 。

可选：将组扩大到其最大大小，或使用最小的条目作为组间隔（2）并在添加间隔（3）时增加左边界。

我认为应该给出最小的组数，因为在步骤2中。我们创建一个无法避免的组，然后在步骤3。我们尽我们所能添加到它中。