在任何给定时间的最大带宽

Question

我们输入了消耗的startTime，endTime和带宽。 like

1234 5678 12 
2345 6789 10 
7900 8790 20 
6790 8123 8 

我们必须计算消耗的最大带宽。如上所述，从输入集{7900 8790}{6790 8123}开始将是28，因为这些集具有交集。

什么是最好的方法来解决它。

Answer 1

使对

通过时间（在领带+第一的情况下）这些对

{t; v} 
where 
t=time 
v = +bandwidth for start of interval or 
    -bandwidth for end of interval 

排序列表。

1234; 12 
5678; -12 
2345; 10 
6789; -10 
7900; 20 
8790;- 20 
6790; 8 
8123; -8 

查看此列表，将v添加到当前带宽值。最大达到值是什么，你需要

1234; 12  : 12 
2345; 10  : 22 
5678; -12 : 10 
6789; -10 : 0 
6790; 8  : 8 
7900; 20  : 28 
8123; -8  : 20 
8790;- 20 : 0 

Answer 2

最简单的方法应该像下面的伪代码，它是O(n lg n)。另外我认为你的答案应该是28，因为[6790，8123]和[7900,8790]也有交集。

Sort_interval() 
int ans = 0, sum = 0; 
For each interval i 
    if interval i intersect with interval i-1 
     sum += bandwidth(i) 
    else 
     ans = max(ans, sum) 
     sum = bandwidth(i) 
Output ans