这个问题能用线性扫描算法解决吗？

Question

编辑：现在我认为这是一种扫描线问题。（请参见底部的更新2）

在这个问题中，我们有N个物体和M个约束条件。（N可以是200k，M可以是100k）。每个物体都是黑色或白色。每个约束条件都是形式为（x,y）的形式，并且意味着在对象x..y的范围内，恰好有一个白色对象；其余的都是黑色。我们想确定最大可能存在的白色对象数量，或者是否无法满足约束条件。

我发现，如果一个约束条件完全包含在另一个约束条件中，则内部约束条件将决定白色对象可以放置的位置。此外，如果有几个不相交的约束条件包含在另一个约束条件中，那么应该是不可能的，因为它违反了每个约束条件只能有一个白色对象的事实。该算法应该足够快，在2-3秒内运行。

更新：其中一个答案提到了精确覆盖问题；这是一个不是NP完全的特殊实例吗？

更新2：如果我们将每个约束条件转换为一个开始和结束事件，并对这些事件进行排序，我们是否可以系统地扫描这些事件并分配白色对象？

- Zheyang Shen

---

此外，如果一个约束条件内包含多个不相交的约束条件，那么这是不可能的，因为它违反了每个约束条件只能有一个白色物体的事实。我不明白何时约束条件既不相交又包含在另一个约束条件中。我假设你所说的“包含在另一个约束条件中”是指形如(x,y)(u,v)的格式，其中x <= u < v <= y，但是显然交集是(u,v)。如果是这种情况，可以通过在最内层约束条件中放置一个白色顶点并将其他最外层约束条件全部涂黑来解决这种嵌套约束条件问题。 - G. Bach

是的，那就是我的意思。现在我想起来了，你认为通过处理/模拟某些东西贪婪地确定白色物体是否可行？ - Zheyang Shen

这可能更适合于http://cs.stackexchange.com... - vonbrand

嗯，我不确定贪心算法是否可行，看起来在减少约束系统后，你应该能够通过使用组合方法来实现。也许思考可以推导出约束系统的归约规则会有所帮助。例如，假设你有三个约束条件 (a,c) (b,f) (d,e)，其中 a<= b <= c < d <= e <=f。然后你就知道可以将 (a,c) 归约为 (a,b)，因为嵌套的约束条件 (b,f) (d,e) 将会强制你将 (b,c) 涂成黑色。这是我开始的地方。我认为还应该有一些比这个示例更详细的归约规则。 - G. Bach

如果您选择减少约束的路线，您将不得不考虑以下规则：a）嵌套和b）交集，这实际上只是完全交集。要找到必须应用缩减规则的约束条件，您可能需要查看区间树。 - G. Bach

Answer 1

您的问题可以表述为一个精确覆盖问题：约束区间形成要被覆盖的集合，每个白色物体覆盖它所在的约束区间。因此，您的问题是找到一个覆盖每个约束区间恰好一次的白色物体子集。

一般来说，精确覆盖问题是NP完全问题，尽管这并不一定意味着它们中的任何特定子集都是。然而，存在算法，如Knuth's Algorithm X（由dancing links实现），可以相当高效地解决大多数这样的问题。

可能您的问题的一维结构也允许更直接的专门解决方法。然而，Algorithm X是攻击这类问题的非常好的通用工具。（例如，最快的数独求解器通常使用类似的算法。）

- Ilmari Karonen

---

这很有趣，但我找不到一个非NP完全问题的解决方案。 - Zheyang Shen

@ZheyangShen 你在哪里发现这个问题的？如果你知道有一个高效的解决方案，我就认为你知道是谁解决了这个问题？ - G. Bach

@G.Bach 不知道源代码是什么。这是我学校ICPC团队的一个练习问题。如果我知道答案，我就不会在这里问了:( - Zheyang Shen

Answer 2

是的，有一种（点）扫描算法。这种算法有点不太优美，但我认为它有效。

首先，对于嵌套的区间进行扫描。按排序顺序处理开始和结束事件（如何解决细节问题由您决定），并保留一个活动区间列表，其中不知道包含另一个区间。要处理开始事件，请添加相应的区间。要处理结束事件，请检查相应的区间I是否已被删除。如果没有，从列表中删除I和I之前的所有剩余区间J。对于每个这样的J，请添加两个区间，其并集是集合差J \ I，添加到黑色区间列表中。

其次，扫描以缩小黑色区间。换句话说，删除已知为黑色的对象，重新编号，并相应调整约束条件。如果整个约束条件都被涂黑，则没有解决方案。

第三，扫描以在现在非嵌套的区间上解决问题。贪心解法可以证明是最优的。

例子：假设我有半开区间约束[0, 4), [1, 3), [2, 5)。第一次扫描创建了黑色区间[0, 1)和[3, 4)。第二次扫描保留了约束[a, c), [a, c), [b, d)。贪心扫描将白色物体放置在新位置a、c、d（旧位置1、4、5）。

第二次扫描的说明：

0 1 2 3 4 5  old coordinates
[       )
  [   )
    [     )
**    **     blackouts
  a b   c d  new coordinates
[       )
  [   )
    [     )

- David Eisenstat

---

你能详细说明第一步吗？如果区间没有完全交叉怎么办？ - Zheyang Shen

“我”始终是“J”的子区间。如果“I1”和“I2”重叠但不嵌套，则什么也不会发生。 - David Eisenstat

在这种情况下，如果它们重叠，区间 I 应该始终在区间 J 中，对吗？ - Zheyang Shen

哦，我还是不明白第二次扫描如何创建列出的3个间隔？ - Zheyang Shen

所以我想问的问题是：如果旧坐标已经被涂黑，你如何将旧坐标映射到新坐标？ - Zheyang Shen