这可以通过线扫描算法解决吗？

Question

编辑:现在我认为这是扫描线问题.(见底部的update2)

在这个问题中,我们给出了N对象和M约束.(N可以200k,M可以100k).每个对象都是黑色或白色.每个约束的形式是(x, y),并且意味着在对象的范围x..y,有正好一个白色物体; 其余的都是黑色的.我们想确定可以存在的最大白色对象数,或者是否不能满足约束条件.

我观察到如果约束完全包含在另一个约束中,则内部约束将指示可以放置白色对象的位置.此外,如果在另一个中包含多个非交叉约束,则应该是不可能的,因为它违反了每个约束只能有一个白色对象的事实.该算法应该足够快,在2-3秒内运行.

更新:其中一个答案提到确切的封面问题; 这是一个非NP完整的专业实例吗？

Update2:如果我们将每个约束更改为开始和结束事件,并对这些事件进行排序,我们是否可以系统地扫描这些事件并分配白色对象？

Answer 1

您的问题可以表示为精确覆盖问题：约束间隔形成要覆盖的集合，并且每个白色对象覆盖其所属的约束间隔。那么，您的问题是找到白色对象的子集，该子集恰好覆盖每个约束间隔一次。

一般来说，精确覆盖问题是 NP 完全的，尽管这显然并不一定意味着它们的任何特定子集都是 NP 完全的。然而，仍然存在可以非常有效地解决大多数此类问题的算法，例如Knuth 的算法 X （通过舞动链接实现） 。

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