找到最小長度，使滑動窗口全長滑動包含給定集合的所有區間

Question

我需要按價格實現產品的分面搜索，即我想高效地生成帶有每個範圍內的產品數量。

由於各種原因，我可以建立作爲一個索引的最好的事情是一個表，每個產品可以使產品的最小和最大可能的價格，如：

 
idProduct | priceMin | priceMax 
1   | 15  | 20 
2   | 2  | 3 
3   | 5  | 7 
4   | 13  | 19 

我們可以假設，所有的數字都自然整數。

要查詢效率，我想找到一個大小s這樣可以保證每個產品，存在一個自然數k，如：

k * s <= priceMin && priceMax <= (k + 1) * s 

換句話說，預 - 計算範圍列表，以便確定給定產品是否落入其中一個範圍內。

使用上面的數據，數字12是用於s一個適當的值，這是因爲：

1 * 12 <= 15 && 20 <= 2 * 12 
0 * 12 <= 2 && 3 <= 1 * 12 
0 * 12 <= 5 && 7 <= 1 * 12 
1 * 12 <= 13 && 19 <= 2 * 12 

然而，數字6是不是s一個合適的值，因爲它不用於產品＃3工作作爲0 * 6 <= 5但7 > 1 * 6

在現實世界中，價格表將有成千上萬的行，所以我正在尋找一種有效的算法，可以讓我找到s的最小可能值。

如果這是一個古典問題，你知道它的名字，我可以從那裏谷歌，但到目前爲止，我無法找到任何相關的東西。

Answer 1

這裏有一個合理有效的算法（O（n + P log P），其中P是最大價格，假設整數價格）。 （我擔心你的限制將使七大洲大，自己的喜好，但EH）

觀察（如一月德沃夏克做第一）的條件

there exists k such that k * s <= priceMin and priceMax <= (k + 1) * s 

相當於

for all k, it holds that k * s <= priceMin or priceMax <= k * s 

相當於

for all k, it does not hold that priceMin < k * s < priceMax. 

證明是不壞，但我不會刻意寫出來。

該算法的第一步是計算開放價格區間(priceMin, priceMax)的聯合作爲位圖。

deltaIntervalCount = [0] * (P + 1) 
for priceMin, priceMax in priceIntervals: 
    deltaIntervalCount[priceMin + 1] += 1 
    deltaIntervalCount[priceMax] -= 1 
intervalCount = [0] * (P + 1) 
for p in range(1, P + 1): 
    intervalCount[p] = intervalCount[p - 1] + deltaIntervalCount[p] 
forbidden = [intervalCount[p] > 0 for p in range(P + 1)] 

該算法的第二步是嘗試增加s的候選人。

for s in range(1, P + 1): 
    if all(not forbidden[k * s] for k in range(P // s + 1)): 
     return s