如何查找所有重叠间隔的总和权重？

Question

Possible Interview Question: How to Find All Overlapping Intervals =>为我们提供了找到所有重叠区间的解决方案。在这个问题之上，想象每个间隔都有重量。当我插入一个新的时间间隔时，我的目标是找到那些重叠区间的总和权重。

条件：新插入的区间的最终值总是大于先前插入的区间的终点，这将导致我们已经排序的终点。

当插入新间隔及其重量时，应检查所有重叠间隔总和权重是否超过限制。例如，当我们插入[15, 70] 2时，[15, 20]的总计权重将为130，并且它应该给出错误，因为它超过了限制= 128，如果不是，新插入的间隔将被附加到列表。

int limit = 128; 
Inserted itervals in order: 
order_come | start | end | weight 
0   [10, 20]  32 
1   [15, 25]  32 
2   [5,  30]  32 
3   [30, 40]  64 
4   [1,  50]  16 
5   [1,  60]  16 
6   [15, 70]  2 <=should not append to the list. 

Final overall summed weight view of the List after `[15, 70] 2` is inserted: 
[60, 70, 2]  
[50, 60, 18]  
[40, 50, 34]  
[30, 40, 98]  
[25, 30, 66]  
[20, 25, 98]  
[15, 20, 130] <= exceeds the limit=128, throw an error. 
[10, 15, 96] 
[5, 10, 64] 
[1, 5, 32] 
[0, 0, 0] 

感谢您宝贵的时间和帮助。

Answer 1

O（log n） - 时间插入可用扩充二叉搜索树进行操作。为了存储

order_come | start | end | weight 
0   [10, 20]  32 
1   [15, 25]  32 
2   [5,  30]  32 
3   [30, 40]  64 
4   [1,  50]  16 
5   [1,  60]  16 

我们有一个树形像

    25 
       / \ 
      /  \ 
      10   50 
      /\  /\ 
      5 20 40 60 
     // /
     1 15 30   , 

每个数字代表从中其继任者的时间间隔。与每个树节点相关联的是两个数字。第一个称为Δweight，定义为节点的间隔的权重减去节点父节点的权重，如果是extent（否则为零）。第二个我们称为Δmax，定义为对应于节点后代的区间的最大权重，减去节点的权重。

对于上面的例子，

interval | tree node | total weight | ∆weight | ∆max 
[1, 5)  1   32    -32  0 
[5, 10) 5   64    -32  0 
[10, 15) 10   96    32  32 
[15, 20) 15   128   32  0 
[20, 25) 20   96    0   32 
[25, 30) 25   64    64  64 
[30, 40) 30   96    64  0 
[40, 50) 40   32    16  64 
[50, 60) 50   16    -48  80 
[60, ∞) 60   0    -16  0 

二叉搜索树的操作几乎总是需要旋转。当我们转动像

p   c 
/\  /\ 
    c r => l p 
/\   /\ 
l g   g r 

一棵树，我们修改

c.∆weight += p.∆weight 
g.∆weight += c.∆weight 
g.∆weight -= p.∆weight 
p.∆weight -= c.∆weight 
p.∆max = max(0, g.∆max + g.∆weight, r.∆max + r.∆weight) 
c.∆max = max(0, l.∆max + l.∆weight, p.∆max + p.∆weight). 

的扩充的要点如下。要查找树中的最大权重，请计算r.∆max + r.∆value其中r是根。为了增加子树中每个权重给定的数量∂，增加子树根的权重∂。通过使用包含排除来更改O（log n）节点，我们可以增加整个区间。总之，这些操作使我们能够评估O（log n）时间的插入。

要查找间隔的总权重，请按正常方式搜索该间隔，同时将该间隔的祖先的Δ权重值相加。例如，为了找到[15,30]的权重，我们寻找15，遍历25（Δ权重= 64），10（权重= 32），20（权重= 0）和15（权重= 32），总重量为64 + 32 + 0 + 32 = 128.

为了找出沿假设间隔的最大总重量，我们做了一个类似这样的修改搜索。使用另一个修改后的搜索，计算最大树值小于或等于start（predstart;让predstart = -∞如果start是所有树值都大于start）并将其传递给maxtotalweight。

maxtotalweight(root, predstart, end): 
    if root is nil: 
     return -∞ 
    if end <= root.value: 
     return maxtotalweight(root.leftchild, predstart, end) + root.∆weight 
    if predstart > root.value: 
     return maxtotalweight(root.rightchild, predstart, end) + root.∆weight 
    lmtw = maxtotalweight1a(root.leftchild, predstart) 
    rmtw = maxtotalweight1b(root.rightchild, end) 
    return max(lmtw, 0, rmtw) + root.∆weight 

maxtotalweight1a(root, predstart): 
    if root is nil: 
     return -∞ 
    if predstart > root.value: 
     return maxtotalweight1a(root.rightchild, predstart) + root.∆weight 
    lmtw = maxtotalweight1a(root.leftchild, predstart) 
    return max(lmtw, 0, root.rightchild.∆max + root.rightchild.∆weight) + root.∆weight 

maxtotalweight1b(root, end): 
    if root is nil: 
     return -∞ 
    if end <= root.value: 
     return maxtotalweight1b(root.leftchild, end) + root.∆weight 
    rmtw = maxtotalweight1b(root.rightchild, end) 
    return max(root.leftchild.∆max + root.leftchild.∆weight, 0, rmtw) + root.∆weight 

我们假设无有Δweight= 0且Δmax=-∞。对不起所有的遗漏细节。

Answer 2

使用的original answer的术语，当你有

'1E 2E 3E ... (n-1)E nE' 

终点已经排序和你的（N + 1）个终点是磨碎机比你只需要找到区间以前的所有端点终点值大于（n + 1）st起点（在闭区间的情况下大于或等于）。

换句话说 - 迭代从最右端点开始到左端的间隔，直到达到端点小于或等于（n + 1）st起点的间隔并跟踪权重。然后检查总和是否符合限制。最坏情况下的时间复杂度是O（n），当所有先前的时间间隔都有终点磨碎机时，则（n + 1）st起点。