在加权间隔调度问题中，有一个间隔 {i_1, i_2, ..., i_n}序列，其中每个间隔i_x代表一个连续的范围（在我的例子中，一个非负整数的范围；例如i_x = [5,9)）。通常的目标是将每个区间的权重设置为等于其宽度，然后确定总权重最大的非重叠区间的子集。我刚刚提供的链接给出了一个很好的解决方案。
我已经用 C++ 实现了该解决方案，从给定链接中提供的算法开始（在此处的 GitHub 存储库中用 Python 编写。
但是，给出的链接上的当前解决方案 - 以及我在其他任何地方看到的讨论 - 只提供了一种捕获单个 maximal fit的方法。当然，在某些情况下，可以有多个最大拟合，每个都具有相同的总（全局最大）权重。
我已经实现了一种“蛮力”方法来捕获所有最大拟合，我将在下面进行描述。
然而，在讨论我使用的蛮力方法的具体细节之前，我想解决的蛮力方法中的关键问题是，除了真正的最大拟合之外，我的蛮力方法还捕获了许多误报. 如果您可以回答以下问题，则无需深入研究我的蛮力方法的细节：
我想知道支持捕获所有最大拟合的基本O(n log(n))解决方案的（或一个）最有效的增强是什么，而不仅仅是一个最大拟合（但如果有人能回答如何避免误报，那也会让我满意）。
我在这方面没有取得任何进展，并且我使用的蛮力方法在最大拟合数超过数千（也许更少）的情况下开始变得难以控制。
谢谢！
我正在使用的蛮力方法的详细信息，仅在感兴趣或有用的情况下：
在我上面链接的现有源代码中有一行代码负责算法选择单个最大拟合的事实，而不是沿着可以捕获所有最大拟合的路径前进。 单击此处查看该行代码。 这里是：
if I[j].weight + OPT[p[j]] > OPT[j - 1]:
注意>（大于号）。这行代码成功地保证了总权重高于给定子问题的任何其他区间组合的任何区间组合。通过更改>为>=，可以捕获所考虑的当前间隔集的总权重与之前的最高总权重相等的场景，这将使得捕获所有最大拟合成为可能。我希望捕捉到这种情况，所以在我的 C++ 迁移中，我使用了and，在等式成立的情况下，我通过递归函数调用>=沿着fork 中的两条路径前进。
下面是（关键）函数的 C++ 代码，该函数捕获每个子问题的所有最佳间隔集（和权重）（注意最终解决方案是在子问题对应于整个问题的最后一个索引处获得的）。
请注意，它OPTs是list所有潜在解决方案中的一个（最大间隔集）（即，其中的每个元素OPTs本身就是所有子问题的单个完整解决方案，由一组间隔和每个子问题的相应权重组成），而OPT用于描述单个这样的完整解决方案 - 与用于构造它的所有间隔的潜在最大拟合，每个子问题一个。
对于我上面指出的加权间隔调度问题的标准解决方案，获得的解决方案只是OPT（单个，而不是列表）。
下面RangeElement代码中的类型只是与我正在讨论的问题无关的元数据。
RangesVec包含作为问题输入的区间集（按结束值正确排序）。 PreviousIntervalVec对应于compute_previous_intervals上面链接中的讨论。
（注意：对于正在查看上面链接的 Python 代码的任何人，请注意，我认为我在其中发现了一个与保存最大集合中的间隔有关的错误；请参阅此处以获取有关此错误的评论，我已经在我下面的 C++ 代码中修复。）
这是我捕获所有最大拟合的“蛮力”实现。 我的蛮力方法还捕获了一些需要在最后删除的误报，我会对任何给出最有效方法来排除误报但使用与以下算法等效的算法的答案感到满意。
void CalculateOPTs(std::vector<std::pair<INDEX_TYPE, std::vector<RangeElement const *>>> & OPT, size_t const starting_index = 0)
{
++forks;
for (size_t index = starting_index; index < RangesVec.size(); ++index)
{
INDEX_TYPE max_weight_to_be_set_at_current_index {};
INDEX_TYPE max_weight_previous_index {};
INDEX_TYPE max_weight_previously_calculated_at_previous_interval {};
INDEX_TYPE current_index_weight = RangesVec[index]->range.second - RangesVec[index]->range.first;
if (index > 0)
{
max_weight_previous_index = OPT[index - 1].first;
}
size_t previous_interval_plus_one = PreviousIntervalVec[index];
if (previous_interval_plus_one > 0)
{
max_weight_previously_calculated_at_previous_interval = OPT[previous_interval_plus_one - 1].first;
}
INDEX_TYPE weight_accepting_current_index = current_index_weight + max_weight_previously_calculated_at_previous_interval;
INDEX_TYPE weight_rejecting_current_index = max_weight_previous_index;
max_weight_to_be_set_at_current_index = std::max(weight_accepting_current_index, weight_rejecting_current_index);
//if (false && weight_accepting_current_index == weight_rejecting_current_index)
if (weight_accepting_current_index == weight_rejecting_current_index)
{
// ***************************************************************************************** //
// Fork!
// ***************************************************************************************** //
// ***************************************************************************************** //
// This is one of the two paths of the fork, accessed by calling the current function recursively
// ***************************************************************************************** //
// There are two equal combinations of intervals with an equal weight.
// Follow the path that *rejects* the interval at the current index.
if (index == 0)
{
// The only way for the previous weight to equal the current weight, given that the current weight cannot be 0,
// is if previous weight is also not 0, which cannot be the case if index == 0
BOOST_THROW_EXCEPTION(std::exception((boost::format("Logic error: Forking a maximal fitting path at index == 0")).str().c_str()));
}
std::vector<std::pair<INDEX_TYPE, std::vector<RangeElement const *>>> newOPT = OPT;
OPTs.emplace_back(newOPT);
OPTs.back().push_back(std::make_pair(weight_rejecting_current_index, std::vector<RangeElement const *>())); // std::max returns first value if the two values are equal; so here create a fork using the second value
OPTs.back()[index].second = OPTs.back()[index-1].second; // The current index is being rejected, so the current set of intervals remains the same for this index as for the previous
CalculateOPTs(OPTs.back(), index + 1);
}
// ***************************************************************************************** //
// If we forked, this is the other path of the fork, which is followed after the first fork, above, exits.
// If we didn't fork, we proceed straight through here anyways.
// ***************************************************************************************** //
OPT.push_back(std::make_pair(max_weight_to_be_set_at_current_index, std::vector<RangeElement const *>()));
if (max_weight_to_be_set_at_current_index == weight_accepting_current_index)
{
// We are accepting the current interval as part of a maximal fitting, so track it.
//
// Note: this also works in the forking case that hit the previous "if" block,
// because this code represents the alternative fork.
//
// We here set the intervals associated with the current index
// equal to the intervals associated with PreviousIntervalVec[index] - 1,
// and then append the current interval.
//
// If there is no preceding interval, then leave the "previous interval"'s
// contribution empty (from the line just above where an empty vector was added),
// and just append the current interval (as the first).
if (previous_interval_plus_one > 0)
{
OPT.back().second = OPT[previous_interval_plus_one - 1].second;
}
OPT.back().second.push_back(RangesVec[index]); // We are accepting the current interval as part of the maximal set, so add the corresponding interval here
}
else
{
if (index == 0)
{
// If index is 0, we should always accept the current interval, not reject, so we shouldn't be here in that case
BOOST_THROW_EXCEPTION(std::exception((boost::format("Logic error: Rejecting current interval at index == 0")).str().c_str()));
}
// We are rejecting the current interval, so set the intervals associated with this index
// equal to the intervals associated with the previous index
OPT.back().second = OPT[index - 1].second;
}
}
}