编辑:现在我认为这是一个扫描线问题。(见底部的update2)
在这个问题中,我们得到了N
对象和M
约束。(N
可以200k
,M
可以100k
)。每个物体要么是黑色的,要么是白色的。每个约束的形式(x, y)
是指在对象的范围内x..y
,只有一个白色对象;其余的都是黑色的。我们想确定可以存在的白色对象的最大数量,或者是否不可能满足约束。
我观察到,如果一个约束完全包含在另一个约束中,则内部约束将决定可以放置白色对象的位置。此外,如果在另一个约束中包含多个不相交的约束,这应该是不可能的,因为它违反了每个约束只能有一个白色对象的事实。该算法应该足够快,可以在 2-3 秒内运行。
更新:其中一个答案提到了确切的封面问题;这是一个不是 NP 完全的特殊实例吗?
更新 2:如果我们将每个约束更改为开始和结束事件,并对这些事件进行排序,我们是否可以系统地扫过这些事件并分配白色对象?