arrays - 是否可以从每个给定的间隔中选择一个数字而不重复选择。线性时间的解决方案

Question

我一直在 hackerearth 实践中尝试这个问题，这需要完成以下工作。

问题

给定一个整数 n，它表示来自 {0,1,2,3,4,5......n-2,n-1} 的 n 个数字的序列

我们以 (L,R) 的形式提供 m 个范围，使得 (0<=L<=n-1)(0<=R<=n-1)

if(L <= R) (L,R) 表示来自上述序列的数字{L,L+1,L+2,L+3......R-1,R}

else (L,R) 表示数字{R,R+1,R+2,......n-2,n-1} & {0,1,2,3.... L-1,L}即数字环绕

例子

n = 5   ie {0,1,2,3,4}
(0,3) signifies {0,1,2,3}
(3,0) signifies {3,4,0}
(3,2) signifies {3,4,0,1,2}

现在我们必须从每个范围中选择一个(仅一个)数字而不重复任何选择。我们必须知道是否可以从每个(和每个)范围中选择一个数字而不重复。

示例测试用例

n = 5// numbers {0,1,2,3,4}
// ranges  m in number //
0 0 ie {0}
1 2 ie {1,2}
2 3 ie {2,3}
4 4 ie {4}
4 0 ie {4,0}

 Answer is "NO" it's not possible.

因为我们不能从范围 4 0 中选择任何数字，因为如果我们从中选择 4，我们将无法从范围 4 4 中选择，如果从中选择 0，我们将无法从 0 0 中选择

我的方法-

1) 它可以在 O(N*M) 中完成，使用递归检查每个范围内的所有选择可能性，并使用 HashMap 并排记录我们的选择。

2)我是按n或m顺序试的，即线性顺序。问题缺乏编辑解释。社论中只提到了一个代码，没有评论和解释。我无法获得通过所有测试用例并被接受的人的代码线性解决方案代码。

我无法理解代码中使用的逻辑/算法以及它为什么有效？

请提出任何线性方法及其背后的逻辑，因为问题有这些限制

  1 <= N<= 10^9
  1 <= M <= 10^5
  0 <= L, R < N

我猜这需要线性或 nlogn 解吗？？

社论中的代码也可以在这里看到http://ideone.com/5Xb6xw

警告 -- 查看代码后，我发现该代码可互换使用 n 和 m 所以我想提一下问题的输入格式。

输入格式

第一行包含测试用例 tc，后面是两个整数 N,M - 第一个表示地球上的国家数，第二个表示他女朋友给他的范围数。之后，接下来的 M 行将有两个整数来描述范围，X 和 Y。如果 (X <= Y)，则范围涵盖国家 [X,X+1...Y]，否则范围涵盖 [X,X+ 1,.... N-1,0,1..., Y].

输出格式

如果可以，打印“YES”，否则打印“NO”。

Answer 1

编辑解决方案有两个组成部分。

线性时间减少到普通间隔的问题

假设输入区间的数量小于 n。

第一个是将问题减少到间隔不环绕的问题，如下所示。给定一个区间 [L, R]，如果 L ≤ R，则发出两个区间 [L, R] 和 [L + n, R + n]；如果 L > R，发出 [L, R + n]。简化的简单方向表明，如果原始问题有解，则简化后的问题也有解。对于 L ≤ R 的 [L, R]，分配一个数字 k，将 k 分配给 [L, R]，将 k + n 分配给 [L + n, R + n]。对于 L > R 的 [L, R]，分配 k, k + n 中属于 [L, R + n] 的那个。除了区间 [L, R] 和 [L + n, R + n] 分别对 k 和 k + n 进行双重赋值外，每个区间都有自己的剩余类 mod n，因此赋值不会冲突。

相反，使用Hall's marriage theorem 证明归约的硬方向(如果原始问题无解，则归约问题无解) .根据 Hall 的标准，对于某些 k，无法解决的原始问题具有一组 k 个输入区间，其并集的大小小于 k。我们首先争辩说存在这样一组输入区间，其并集是一个(循环)区间(假设不全是 0..n-1)。将并集分解为构成它的最大(循环)区间集。每个输入区间恰好包含在这些区间之一中。通过平均参数，一些最大(循环)间隔包含比其大小更多的输入间隔。我们通过将这个反例“提升”到减少的问题来完成。给定最大(循环)区间 [L*, R*]，如果 L* ≤ R*，我们将其提升到普通区间 [L*, R*]，如果 L* >，则提升到 [L*, R* + n] R*。对这个区间中包含的循环区间也做同样的事情。证明这个提升的反例满足霍尔准则是乏味但直接的，这意味着简化的问题无解。

普通区间的 O(m log m) 时间解

这是一种扫描线算法。按较低端点对间隔进行排序并按该顺序扫描它们。我们想象扫描线从下端点移动到下端点。维护与扫掠线相交且未分配编号的间隔集，按上端点排序。当扫描线即将移动时，将新旧位置之间的编号分配给集合中的区间，优先分配给上端点最低的区间。这个策略的正确性应该很清楚:可以分配一个数字但被传递的间隔至少有与分配的间隔一样多的选项(在超集的意义上)，所以我们永远不会做出选择我们有理由感到遗憾。