有没有一种多项式算法可以找到整数分配给区间的方案？

Question

我有以下问题：给定一个时间间隔的列表和一个整数k，是否存在将值<= k分配给时间间隔的方案，使得没有两个重叠的时间间隔具有相同的值？是否存在一种多项式算法来解决这个问题？我认为可以用动态规划来解决，但我想不出解决方案。

- German

---

据我理解，这正是决定一个“区间图”是否可k-着色的问题。虽然我对这个主题不太了解，但这些概念是算法文献中提到该问题时所使用的。 - Codor

你不能只按左端点对区间进行排序，然后贪心地一遍扫描，为每个区间分配适合的任何值吗？ - user2357112

也许吧，我正在四处寻找确认。 - Codor

我不明白问题所在。你能给个例子吗？ - Colonel Panic

我认为你的问题等同于在O(nlogn)时间复杂度内找到最大数量的相交区间。 - piotrekg2

Answer 1

你有 k 台机器和一堆任务（时间间隔）即将到来，每个任务都有一个开始和结束时间。每个任务将占用一台机器的时间间隔。你想知道是否能处理所有的任务。

当一个任务到达时，你可以将其分配给任何未被占用的机器，只要有空闲的机器即可。同样地，哪些机器被占用并不重要，只要关注运行的任务即可。在机器1上运行2小时后完成的任务与在机器3上运行2小时后完成的任务是相同的；无论如何，你都需要占用一台机器的时间为2小时。 你的决策是无关紧要的。 在任何时候，都有一组正在运行的任务和一些未被占用的机器。这就是唯一重要的事情。

基于此，以多项式时间做这件事情非常容易。只需按左端点对时间间隔进行排序，并在一次遍历中贪心地分配每个时间间隔适合的值即可。如何跟踪哪些机器被占用将影响你的运行时间，但几乎任何跟踪方法仍然需要多项式时间。

- user2357112

---

虽然我完全同意你的答案，但我认为“你的决定毫无意义”的评论有点误导人。毕竟，你的答案所采用的方法基本上是对着色算法的重新表述。 - Codor

假设你有10台机器和10小时的时间来完成所有任务。这些任务分为90个1小时的间隔和1个10小时的间隔。贪心算法在这里会失败。 - Dave

@DaveGalvin：每个任务都有一个开始时间和结束时间，而不仅仅是长度。 - user2357112

@user2357112 哎呀，你说得对。 - Dave

Answer 2

这可以通过一个简单的贪心算法和两个栈来解决：一个是区间/整数对的栈（最初为空），另一个是整数的栈（最初填充了0到k）。

按开始时间排序区间并迭代它们。对于每个区间，首先迭代一下整数对的栈，并弹出每个结束时间在当前区间开始时间之前的区间。弹出区间时，将相关联的整数推回整数栈中。然后，从整数栈中弹出一个整数，并将其与当前事件一起推入到对栈中。

如果任何时候整数栈用完，则问题无解。解决方案是将区间/整数对按照推入顺序推入到栈中的。

---

另一个没有最大k限制的替代解决方案也很容易：如果整数栈为空，则增加k并使用它代替。

如果使用按结束时间排序的优先队列来存储区间/整数对，则该算法在最坏情况下应为O(nlogn)。

- orlp

Answer 3

尽管没有提供证明，但是维基百科文章关于区间图的内容提到了一个结果，即按左边界的非递减顺序考虑区间，并贪心地分配最低可能的颜色可以得到最优结果。

显然，更详细的讨论可以在以下教材中找到。

引用：

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

请注意，根据维基百科文章关于图着色的内容，区间图的色数恰好等于团数。

- Codor

Answer 4

你的问题等同于在O(nlogn)时间内找到最大数量的相交区间。

证明：假设对于一组区间S，k是从S中相交区间的最大数量。显然，为了进行有效分配，我们必须至少使用k个数字。现在我们需要证明k是足够的。让我们按升序迭代S中的区间。每次打开一个新的区间时，我们从未使用过的数字集合中选择一个数字，每次关闭一个区间时，我们将数字放回该集合。显然，k个数字的集合就足够了。

相应的 C++ 代码：

bool canAssign(const std::vector<std::pair<int, int>> &intervals, int k)
{
    const int left = 0, right = 1;

    std::vector<std::pair<int, int>> ends;
    for (const auto &interval: intervals)
    {
        ends.emplace_back(interval.first, left);
        ends.emplace_back(interval.second, right);
    }

    std::sort(ends.begin(), ends.end());

    int maxStack = 0, stack = 0;
    for (const auto &end: ends)
    {
        if (end.second == left)
            ++stack;
        else
            --stack;

        maxStack = std::max(maxStack, stack);
    } 

    return maxStack <= k;
}

- piotrekg2