给定 N 个人，其中一些是敌人，找出没有敌人的区间数

Question

一个朋友给了我这个问题作为挑战，我试图在 LeetCode 上找到这样的问题，但遗憾的是找不到。

问题

Given a line of people numbered from 1 to N, and a list of pairs of M enemies, find the total number of sublines with people that contain no two people that are enemies.

Example: N = 5, enemies = [[3,4], [3,5]]

Answer: 9

Explanation: These continuous subintervals are:

[1,1], [2,2], [3,3], [1,2], [2,3], [1,3], [4,4], [4,5], [5,5]

我的做法

我们将非冲突区间定义为从（包括）[a,b] 开始的连续区间，其中在该区间内没有两个人是敌人。

逆向计算，如果我知道 [1,3] 中有一个不冲突的间隔，就像上面给出的示例一样，我知道这两个数字之间的连续间隔数是 n(n+1)/2，其中 n是区间的长度。在这种情况下，间隔长度为 3，因此在 [1,3] 之间（包括在内）有 6 个间隔。

扩展这个逻辑，如果我有一个 所有非冲突间隔 的列表，那么答案就是每个间隔长度 (n_i*(n_i+1))/2 的总和 n_i.

然后我需要做的就是找到这些间隔。 这就是我卡住的地方。

我真的想不出类似的编程问题。这看起来很相似，但与 leetcode 上的 Merge Intervals 问题要求的相反。在那个问题中，我们被赋予了 良好的间隔 并被要求将它们组合起来。在这里我们遇到了坏处。

有指导吗？

编辑： 我能想到的最好的：

这个有用吗？

所以让我们把max_enemy[i]定义为小于某个人i的最大敌人，其中i是通常的[1,N]。我们可以使用以下循环在 O(M) 时间内生成此值：

max_enemy = [-1] * (N+1) # -1 means it doesn't exist
for e1, e2 in enms:
    e1, e2 = min(e1,e2), max(e1, e2)
    max_enemy[e2] = max(max_enemy[e2], e1)

然后如果我们通过 person 的数组保持滑动 window。一旦我们找到一个 i 的人 window，滑动 window 就会结束：max_enemy[i] < i。这样我们就知道包括这个人会打破我们的连续区间。所以我们现在知道我们的间隔是 [s, i-1] 并且我们可以做我们的数学。我们重置 s=i 并继续。

这是视觉上如何工作的可视化。我们在任意两个敌人之间画一条路径：

N=5, enemies = [[3,4], [3,5]]

1   2   3   4  5
        |   |  |
        -----
        |      |
        --------

EDIT2: 我知道这对 N=5, enemies=[[1,4][3,5]] 不起作用，目前正在修复，仍然卡住

Answer 1

有一种很酷的视觉方式可以看到这个！

我们不关注线，而是看玩家对矩阵。如果 ii 和 j 是敌人，那么这种敌对的效果恰恰是从考虑中消除 (1) 这个区间，以及 (2) 任何严格大于它的区间。因为敌对是对称的，我们不妨只看矩阵的右上半部分，以及对角线；我们将使用字符

"X"表示一对是敌人，
"*"表示一对已经被一对敌人遮挡，并且
"%" 在下半部分将其标记为不属于上半部分矩阵。

对于你代码中的两个例子，观察它们对应的矩阵：

# intervals:  9                   # intervals:  10

 0   1   2   3   4                 0   1   2   3   4      
------------------------          ------------------------
             *   *   | 0                        *   *   | 0           
 %           *   *   | 1            %           X   *   | 1           
 %   %       X   X   | 2            %   %           X   | 2           
 %   %   %           | 3            %   %   %           | 3           
 %   %   %   %       | 4            %   %   %   %       | 4

下面提供的简单解决方案在 O(N^2 M) 时间内解决了问题 O(N^2) space。

def matrix(enemies):
    m = [[' ' for j in range(N)] for i in range(N)]
    for (i,j) in enemies:
        m[i][j] = 'X' #Mark Enemiship
        # Now mark larger intervals as dead.
        for q in range(0,i+1):
            for r in range(j,N):
                if m[q][r] == ' ':
                    m[q][r] = '*'

    num_int = 0
    for i in range(N):
        for j in range(N):
            if(j < i):
                m[i][j] = '%'
            elif m[i][j] == ' ':
                num_int+=1

    print("# intervals: ", num_int)
    return m

为了进一步说服自己，这里是矩阵，其中

玩家2与自己为敌，所以有一道屏障，在[0,1]和[3,4]区间有两个较小版本的谜题，每一个都承认3个子区间)
每个玩家都与他们左边两个人为敌，所以只允许长度-(1 或 0) 间隔（其中有 4+5=9 个间隔）

# intervals:  6                   # intervals:  9

 0   1   2   3   4                 0   1   2   3   4      
---------[===========+              --------[============+
         *   *   *  || 0                    X   *   *  || 0           
 %       *   *   *  || 1            %           X   *  || 1           
 %   %   X   *   *  II 2            %   %           X  II 2           
 %   %   %           | 3            %   %   %           | 3           
 %   %   %   %       | 4            %   %   %   %       | 4

复杂性：在数学上与排序列表或验证列表排序相同。也就是说，在最坏的情况下 O(M log M)，O(M) space 进行排序，在最好的情况下仍然至少 O(M) 时间来识别列表是否已排序。
奖金：这也是一个很好的例子，说明了看待问题而不是解决方案的力量。这样看待问题的观点也将提供更明智的解决方案。我们显然可以比我上面给出的代码做得更好...

例如，如果我们可以计算未着色点的数量，即覆盖敌舰的最小凸多边形的面积，以及两个边界点，我们就很清楚了。（找到额外的两个点可以在 O(M) 时间内完成。）现在，这可能不是您可以在睡眠中解决的问题，但幸运的是，寻找凸包的问题非常自然 the algorithms used to do it are well known.

特别是 Graham Scan 可以在 O(M) 时间内完成，只要我们恰好给定成对的敌人，以便对其中一个坐标进行排序。更妙的是，一旦我们有了凸包中的一组点，就可以通过将其分成最多 M 个轴对齐的矩形来计算面积。 因此，如果敌人对被排序，整个问题可以在 O(M) 时间内解决。 请记住 M 可能比 N 显着，我们甚至不需要在数组中存储 N 个数字！这对应于该问题的其他答案中建议跳过行的算法。

如果它们未排序，其他 Convex Hull 算法会产生 O(M log M) 运行时间，O(M) space，如所示。其实这就是一般的下界！这可以用更复杂的几何简化来表示：如果你能解决这个问题，那么你可以计算每个数字的高度之和，乘以它到“新零”的距离，满足 j+i = N 的代理.这个总和可以用来计算到对角线的距离，这足以在 O(M) 时间内对数字列表进行排序——对于对抗性输入来说，这个问题在 O(M log M) 时间内是无法解决的。

啊，那么为什么我们可以通过手动执行此集成来获得 O(N + M) 解决方案，就像在其他解决方案中明确完成的那样？这是因为如果我们知道它们落入 N 个箱子，我们可以按 Bucket Sort.

对 M 个数字进行排序

感谢分享拼图！

Answer 2

您可以在 O(M log M) 时间和 O(M) space.

内解决此问题

令 ENDINGAT(i) 为在 position/person i 处结束的无敌人间隔的数量。这也是以i结尾的最大无敌区间的大小。

您寻求的答案是每个人 i 的所有 ENDINGAT(i) 的总和。

让 NEAREST(i) 成为第 i 个人之前最近的第 i 个敌人。如果我没有前面的敌人，就设为-1。

现在我们可以写一个简单的公式来计算所有的 ENDINGAT(values):

ENDINGAT(1) = 1，因为只有一个区间以 1 结尾。对于更大的值：

ENDINGAT(i) = MIN( ENDINGAT(i-1)+1, i-NEAREST(i) )

所以，只要我们能把所有的NEAREST(i)都排好，就很容易按顺序计算出所有的ENDINGAT(i)。为此，您需要做的就是按最高成员对敌人对进行排序。然后对于每个 i 你可以遍历以 i 结尾的所有对以找到最接近的对。

就是这样 - 事实证明这很容易。时间主要由排序敌人对所需的 O(M log M) 时间决定，除非 N 比 M 大得多。在这种情况下，您可以跳过没有前面敌人的人的 ENDINGAT 运行，计算他们对数学求和。

给定 N 个人，其中一些是敌人，找出没有敌人的区间数

Given N people, some of which are enemies, find number of intervals with no enemies

algorithm

math

sliding-window

问题

我的做法

这个有用吗？