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

Question

一个 friend 给了我这个问题作为挑战，我试图在 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 ，因此在 6 之间(并包括)有 [1,3] 间隔。
扩展这个逻辑，如果我有 所有非冲突区间 的列表，那么答案就是每个区间长度 (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)

然后，如果我们通过保持滑动窗口的人的数组。一旦我们找到一个人 i ，它就会结束滑动窗口: 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

有一种很酷的视觉方式可以看到这一点!
与其关注这条线，让我们看看玩家对的矩阵。如果 i i 和 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) 空间中的问题。

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) 空间，最好的情况下仍然至少有 O(M) 时间来识别列表是否已排序。
奖励:这也是一个很好的例子，说明了看待问题的身份，而不是它的解决方案的力量。 对问题的这种看法也将为更明智的解决方案提供信息。我们显然可以比我上面给出的代码做得更好......
例如，如果我们可以计算未着色点的数量，即覆盖敌人的最小凸多边形的面积，以及两个边界点，我们就很清楚了。 (找到两个额外的点可以在 O(M) 时间完成。)现在，这可能不是你在睡梦中可以解决的问题，但幸运的是，找到凸包的问题是如此自然，以至于 the algorithms used to do it are well known 。
特别是， Graham Scan 可以在 O(M) 时间内完成，只要我们碰巧得到一对敌人，以便对它们的一个坐标进行排序。更好的是，一旦我们在凸包中获得了一组点，就可以通过将其划分为最多 M 轴对齐的矩形来计算面积。 因此，如果敌人对被排序，整个问题可以在 O(M) 时间内解决。 请记住， M 可能比 N 显着，我们甚至不需要在数组中存储 N 个数字!这对应于在这个问题的另一个答案中提出的跳过行的算法。
如果它们没有排序，其他凸包算法会产生一个 O(M log M) 运行时间，带有 O(M) 空间，由 @Matt Timmermans's solution 给出。其实这就是一般的下界!这可以用更复杂的几何简化来表示:如果你能解决这个问题，那么你可以计算满足 j+i = N 的代理的每个数字的高度之和，乘以它到“新零”的距离。这个总和可用于计算到对角线的距离，这足以在 O(M) 时间对数字列表进行排序——这是一个无法在 O(M log M) 时间下解决对抗性输入的问题。
啊，那么为什么我们可以通过手动执行此集成来获得 O(N + M) 解决方案，就像在其他解决方案中明确完成的那样？这是因为如果我们知道它们落入 N bins，我们可以通过 Bucket Sort 对 M 个数字进行排序。
感谢分享拼图!