在任何給定時間的最大帶寬

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