在给定的N辆汽车序列中找到最大的紫色汽车数量。(参见描述)

Question

从1到N的一排有N辆车，一个人拍M的汽车照片。每一张照片中出现的汽车都是由元组(i，j)给出的，这意味着从i到jth汽车的所有汽车都会出现在照片中。

请注意，所有的照片不需要覆盖每辆车。一辆汽车可以出现在一张以上的照片中。

每一张照片上都有，正好是一辆紫色轿车。找到最大数量的紫色汽车可能。如果不可能打印-1。

输入:第一行包含N和M。下一行包含M对(x，y)，它表示从xth car到yth car的汽车照片。输出:最大数量的紫色汽车可能。

例子：

输入

5 1

(3 )5

输出：3

说明:只有一辆车从3到5可以是紫色的。车1和车2将是紫色的，以使紫色汽车的数量最大化。

输入

5 1

( 4 )

输出：5

输入

5 3

(1 )、(3 )、(3、4)

输出：1

说明:3或4都可以是一辆紫色的汽车。

输入

5 2

(1，4)，(2，5)

输出：2

说明:车1和车5可以是紫色的。

输入：

10 3

(1 )、(6、10)、(1、10)

输出：-1

说明:在这种情况下，每隔一段时间都不可能有一辆紫色的车。

Answer 1

如果我没有弄错，这个问题可以作为网络问题来解决，如下所示。

网络的节点集具有源节点s和终端t；设想接收器位于最左边，终端位于最右边，流量从左到右。在s旁边，为每辆车放置一个节点，并将s连接到每辆车。在car节点旁边，为每个间隔创建一个节点。现在从car节点开始，创建到t的路径，遍历区间节点集；路径通过包含car的每个间隔。

除了s和t之外，每个节点中的流都被限制为精确的1，即每间隔精确的1 car必须被着色为紫色；弧不需要显式地受到约束。最后，通过一定的网络流量算法，使s到t的流强度最大化。将其节点具有非零流的每辆车涂上紫色。如果实例不允许可行流，则初始问题实例是不可行的。

Answer 2

注意，如果有一张完全被另一张照片覆盖的照片，我们只需要关心外面的照片(琐碎的)。

第二项意见：

现在，在删除所有覆盖的照片(如上文所述)之后，我们将看到这样的情况：

我们有n张照片，可以分为几组，每组都是一组m照片：(a1, b1) , (a2, b2) ... , (am, bm)和a1 < a2 and b1 > a2 ... or ai < a(i + 1) and bi > a(i + 1)。

我们注意到，如果我们选择第一张紫色的汽车作为第一张照片的范围(a1, a2)，并且继续以这种方式选择汽车(第一个还没有被任何汽车覆盖的范围)，这总是最优的。证明：

• 如果我们选择range (a1, a2)中的汽车，那么下一辆车可以选择range (b1 , bm)，否则，如果我们选择其他汽车(在range (a2,b1)中)，那么选择下一辆车的范围就会更小(很容易看到)，所以，选择range (a1, a2)中的汽车会给出最优的结果。

如果实现扫描线算法，时间复杂度将是O(m log m)。

备注：该算法只有在照片集有效的情况下才有效，否则，我们需要检查它的有效性。

Update：正如PeterdeRivaz所指出的，我们需要处理一个特例:当有两个或更多的照片时，两者都涵盖一张照片，因此，我们需要加入所有这些照片。