您将如何使用排序来查找某些整数范围的并集之间是否存在差距

Question

>假设您的范围声明了从 0 到 N

这些范围采用 [a，b] 的形式，其中 0<=a,b<=N

为了确定联合之间是否存在差距，我可能会对所有a, b值进行排序，并明确哪个是起点，哪个是终点。

然后我会扫描它，如果终点和起点之间有间隙，那么我们就会找到一个间隙，所以我们完成了。

这是对的吗？

Answer 1

这基本上就是这个想法，但你必须处理重叠的范围。最简单的方法是忽略起点和终点之间的联系，只查看给定点的范围计数：

例如，下面是一些范围：

                                     ----------
                       -------------------     ---  -------
                 -----------         ---------------  ----    ----
Vertical count: 011111122222111122222333332222222211111111100011110
The union:       ------------------------------------------   ----

在原始范围集中，有些点最多在三个范围内（即使这只是任意的）。我们可以通过对起点和终点进行排序来计算计数，从而计算联合，然后简单地从左到右扫描。

如果我们从范围的左侧开始（例如，从 -1 处），我们就处于 0 范围内的一个点。当我们向右移动时，我们将到达起点和终点。越过起点会增加我们所处的范围数量;越过终点会减少终点。我们不需要知道哪个起点对应于哪个终点来保持范围数量的准确计数。

我们可以在扫描时计算并集，方法是从一个空向量开始，然后在范围计数从 0 变为正值时插入一个起点，当范围计数从正值变为 0 时插入一个终点。（由于此示例中的范围是完全包含的，因此我们需要小心处理扫描中结束点之前的起点。如果我们向联合添加多个起点，则联合是不相交的。