我也還沒找到 O(n) 的作法，不過分享一下我到目前為止的想法。
首先假設這 K 個 occurrences list 各自是排序過的
lists = {list_1, list_2, ..., list_K}
where list_i = {p_i1, p_i2, ...}
不失一般性的假設 |list_1| (list_1 的元素個數) 是最小的
我們知道 the smallest window 一定會包含 p_11, p_12, ... 的其中一個
假設包含 p_1j
那對 list_i (i != 1) 來說，所要找的 window 一定會包含
a_i = max {p_ik | p_ik <= p_1j} 和
b_i = min {p_ik | p_ik >= p_1j} 的其中一個
於是，我們就可以得到一個小一點的問題，
lists = {list_1, list_2, ..., list_K}
where list_1 = {p_1j},
list_i = {a_i, b_i}
這個問題的大小是 O(K) ，如果可以在 O(K) 的時間得到答案的話，
我們就可以用 O(N) 的時間得到原問題的答案：
// all indices start from 1
Given lists
swap( lists[1], arg min { |lists[i]| } ) // O(N)
for i = 2, ..., K // This for loop can be done in O(N)
lists[i].push_back(INF) // 加入這兩個邊界可以讓下面的程式簡單
lists[i].push_front(-INF) // 一些
a = { 0, 0, ..., 0} // size = K
b = { 1, 1, ..., 1} // size = K
answer = INF
for i = 1, ..., |lists[1]|
for j = 2, ..., K
while lists[j][a[j] + 1] <= lists[1][i]
a[j] = a[j] + 1
while lists[j][b[j] + 1] >= lists[1][i]
b[j] = b[j] + 1
sub_lists[1] = { lists[1][i] }
for j = 2, ..., K
sub_lists[j] = { lists[j][a[j]], lists[j][b[j]] }
tmp = solve(sublists)
if (tmp < answer)
answer = tmp
return tmp
其中 a[j] = a[j] + 1 和 b[j] = b[j] + 1 的總運算量是 O(N)
所以，整個的運算量是
O(N) + O(N) + O(N) + O(|lists[1]| * O(solve(sublists))
如果 O(solve(sublists)) = O(K) 的話，因為 |lists[1]| <= N/K (因為他是最小的)
所以 O(|lists[1]| * O(solve(sublists)) = O(N)
整個的運算量就會是 O(N)
另外，因為 solve(sublists) 這個問題和原本的問題有很高的相似性，
如果原本的問題可以在 O(N) 的時間算完，
那 solve(sublists) 就可以在 O(K) 的時間算完。
反過來說，如果 solve(sublists) 不可能 在 O(K) 的時間算完
那原問題也 不可能 在 O(N) 的時間算完
(原命題為真，則逆否命題也為真)
很可惜的，解 sublists 我目前只想到 O(K logK) 的算法， O(K) 只能得到一些上界
補充1 ：
solve(sublists) 可以再換成另一個等價的問題：
給定 a = { a_1, ..., a_(K-1) }, b = { b_1, ..., b_(K-1) }
for all i, a_i, b_i >= 0,
a 和 b 並沒有被排序過，且 a_i > 0 iff b_i > 0
目標：minimize A + B
subject to: for all i, either a_i <= A or b_i <= B
幾個可以在 O(K) 算出來，可是不知道有沒有用的東西：
max a_i (A <= max a_i)
max b_i (B <= max b_i)
max {min {a_i, b_i}}
a 的第 k 名
b 的第 k 名