这可以用线扫算法解决吗？
编辑：现在我认为这是一个扫描线问题。 （见底部的更新2）
在这个问题中，我们给出了N对象和M约束。 （ N可以是200k ， M可以是100k ）。 每个对象都是黑色或白色。 每个约束都是以(x, y)的形式表示的，并且意味着在对象x..y的范围内，只有一个白色对象; 其余的都是黑色的。 我们想要确定可能存在的白色物体的最大数量，或者是否无法满足约束条件。
我观察到，如果一个约束完全包含在另一个中，内部约束将决定一个白色物体的放置位置。 另外，如果在另一个中包含多个不相交的约束条件，则应该是不可能的，因为它违反了每个约束条件只能有一个白色对象的事实。 该算法应该足够快以在2-3秒内运行。
更新：其中一个答案提到确切的封面问题; 这是一个不是NP完全的专业实例吗？
Update2：如果我们将每个约束更改为开始和结束事件并对这些事件进行排序，我们是否可以系统地扫描这些事件并分配白色对象？
你的问题可以表示为一个精确的覆盖问题：约束区间形成了要覆盖的集合，每个白色物体覆盖了它所在的约束区间。 那么你的问题就是找到一个白色物体的子集，它只覆盖每个约束间隔一次。
确切的覆盖问题一般是NP完全的，尽管这显然不一定意味着它们的任何特定子集。 然而，仍然存在算法，如Knuth的算法X（通过跳舞链接实现），可以非常有效地解决大多数这样的问题。
您的问题的一维结构可能也可能允许更直接的专业解决方法。 然而，算法X是攻击这些问题的非常好的通用工具。 （例如，最快的数独解算器通常使用类似的东西。）
是的，有一个（点） - 扫描算法。 这是一种不雅，但我认为它的作品。
首先，扫描嵌套的间隔。 以排序的顺序处理开始和结束事件（留给你的平局）并且保留不知道包含另一间隔的活动间隔的列表。 要处理开始事件，请附加相应的时间间隔。 要处理结束事件，请检查相应的时间间隔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
[ )
[ )
[ )