在向量中查找对的最快方法，在迭代时将其删除

Question

我目前正在研究一种贪婪算法，它类似于活动选择问题。我有对向量（自然数），按第二个值排序。对于每一对，我采取可能最接近的一对（最接近的意思是（p2.first - p1.second）是最小的，p1.second

下面是示例。每一列是对的索引，每行是对的范围。例如，对 [0] = [0，3]。在第一次迭代后，对 [0] 应转换为 [0，9]，第二列应删除。

Answer 1

真的很难说做任何事情的“最快方法”是什么。即使“足够快”在不知道你的约束的情况下也是有问题的。因此，我将为您提供一些技巧，以获得（可能）“更快”的程序;它是否足够快由您决定。

首先，您可能想要更改排序标准。与其对第二个组件进行排序（我假设区间结束），不如对第一个组件进行排序，然后对第二个组件进行排序。这样，开始较早的间隔将在数组中较早，并且在具有相同开始的间隔中，最短的间隔将排在第一位。

其次，您可能希望有一个帮助程序数据结构：一个自然排序的对数组，其中每个对的第一个分量是任意数字 X，第二个分量是从 X 开始的（排序的）原始数组中第一对的索引。例如，问题中图像的这个数组将是 {{0， 0}， {4， 1}， {9， 2}}。不难看出如何在 O（n） 中构造这个数组，以及如何使用它来加速对原始数组的搜索到摊销的 O（1）。

第三，要遍历 std：：vector 并毫无问题地删除其元素，您可以使用索引而不是迭代器。但是，这不是特别有效，因为每次擦除都必须向后移动相当多的元素，甚至可能重新分配矢量并复制/移动其所有元素。相反，做你现在正在做的事情，用独特的数字标记你想要删除的元素，在你的算法完成后，只需再次检查数组并将它们全部删除。以下是伪代码：

displacement = 0
for all elements in the array, do:
    if current element should be removed, then:
        increment "displacement"
    else:
        move current element back "displacement" places

delete last "displacement" elements

编辑：阅读您的评论后，您不需要任何这些东西。只需按照我上面写的方式（即按字典顺序）对数组或对进行排序，然后从中构建另一个对数组，如下所示：

let original vector be A, and the new vector of pairs be B,
t0 = -1
t1 = -1
for all elements in A, do:
    if start time of current element is greater than "t1", then:
         append the pair (t0, t1) to B
         t0 = start time of current element
         t1 = end time of current element
    else:
         t1 = max(t1, end time of current element)
append the pair (t0, t1) to B
remove first element of B (because it is (-1, -1))

（我的方式并不完全优雅，但它可以完成工作。

然后在这个新数组 B 上运行成本计算逻辑。这个新数组将更短，并且其元素之间不会有重叠。