c++ - 在 vector 中找到对的最快方法，在迭代时将其删除

我目前正在研究一种贪婪算法，该算法类似于“ Activity 选择问题”。我有成对的 vector (自然数)，按第二个值排序。对于每对，我可能会选择最接近的对(最接近的我的意思是(p2.first-p1.second)最小，而p1.second
以下是示例。每列是对的索引，在每一行是对的范围。例如，pairs [0] = [0,3]。第一次迭代后，对[0]应转换为[0,9]，第二列应删除。

最佳答案

真的很难说什么是“最快的方法”。即使“足够快”，也无法准确了解您的约束条件。因此，我将为您提供一些提示，以获取(可能)“更快”的程序；是否足够快取决于您自己决定。

首先，您可能想更改排序标准。无需对第二个组件进行排序(我假设间隔的结尾)，您需要对第一个组件进行排序，然后对第二个组件进行排序。这样，开始时间越早的间隔将在数组中越早，而在开始时间相同的间隔中，最短的间隔将是第一个。

其次，您可能需要一个辅助数据结构:自然排序的对数组，其中每个对的第一个成分是任意数字X，第二个是开始的(排序的)原始数组中第一对的索引例如，在您的问题中，该图像的数组将为{{0，0}，{4，1}，{9，2}}。不难看出如何在O(n)中构造此数组以及如何使用它来加快对原始数组的搜索，以摊销O(1)。

第三，要遍历std::vector并毫无问题地删除其元素，可以使用索引而不是迭代器。但是，这并不是特别有效，因为每个erase必须向后移很多元素，甚至可能重新分配 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上运行成本计算逻辑。这个新数组将更短，并且其元素之间不会重叠。

关于c++ - 在 vector 中找到对的最快方法，在迭代时将其删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53770888/