演算法高階・堆積與優先佇列
單一 worker 的排程、滑動視窗中位數、多來源日誌對齊的最小時間窗。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 01
單一 worker 的短任務優先
困難堆積一台只有單一 worker 的機器處理排入的任務。每個任務有編號、排入時間與執行時間。規則:
- worker 閒著時,從「已排入(排入時間 ≤ 目前時間)而且還沒執行」的任務裡,挑執行時間最短的;一樣短挑編號小的
- 開始後就做到完成,中間不換手;完成的那一刻就能挑下一個
- 閒著而且沒有已排入的任務時,時間直接跳到下一個任務排入的時間
一開始的時間是 0。
輸入:
第 1 行:任務數 n
接下來 n 行:
編號 排入時間 執行時間(整數,編號彼此不同;行的順序不代表排入順序)輸出:兩行
第 1 行:任務的執行順序(編號以空白分隔)
第 2 行:所有任務的等待時間總和(每個任務的等待時間=開始時間−排入時間)
要求:任務依排入時間排序後用指標逐一放進 heap,heap 的鍵是 (執行時間, 編號);不要每挑一次就掃過全部任務。
範例輸入:
5
1 0 7
2 2 3
3 2 3
4 3 1
5 30 2
範例輸出:
1 4 2 3 5
19
類型對應:LeetCode「Single-Threaded CPU」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 02
延遲的滑動中位數告警
困難堆積/有序結構監控系統對 API 回應時間(毫秒)算「最近 k 筆的中位數」:k 是奇數時取正中間那個,k 是偶數時取中間兩個的平均。每來一筆新資料,視窗就往後移一格,從第 1 到第 k 筆組成第 1 個視窗開始算。中位數嚴格大於門檻的視窗要告警。
輸入:
第 1 行:組數 t
接下來 t 行:
k 門檻 回應時間...(整數,以空白分隔),或GEN k 門檻 n seed lo hi(由 starter 的gen(n, seed, lo, hi)產生回應時間)。GEN開頭的行是大量測資的縮寫:starter 已寫好gen(),讀進來後跟一般的 list 一樣,不用自己處理。輸出:每組一行
- 資料筆數少於 k:印
NO WINDOW - 否則印
最大中位數 告警視窗數 第一個告警視窗:最大中位數印到小數點後 1 位;第一個告警視窗是它的起始位置(從 1 起算),沒有告警印-
要求:用一個隨視窗維護的有序結構(兩個 heap 加延遲刪除,或
bisect.insort維護排序 list)取中位數;不要每個視窗都重新 sort。範例輸入:
2
3 100 90 120 80 130 140
2 10 5
範例輸出:
130.0 2 2
NO WINDOW
類型對應:LeetCode「Sliding Window Median」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答 - 資料筆數少於 k:印
- 03
對齊多個來源的最小時間窗
困難堆積排查一起事故時,要把幾個系統的日誌對齊:每個來源各有一串已排序的事件時間戳(秒)。請找出最小的時間窗 [L, R](L、R 都是某筆事件的時間戳),讓每個來源都至少有一筆事件落在窗內。窗的大小是 R−L;一樣小時取 L 較小的。
輸入:
第 1 行:組數 t
每組:第 1 行是來源數 k;接下來 k 行各是
來源名 時間戳...(時間戳由小到大,可重複,至少一筆)輸出:每組一行
L R。要求:每個來源放一個指標,用 heap 取目前最小的時間戳,同時記住目前的最大值;每次把最小的那個來源往後推一格。不要列舉每個來源各挑一筆的所有組合。
範例輸入:
1
3
api 100 140 210
db 130 200
queue 120 205 300
範例輸出:
200 210
類型對應:LeetCode「Smallest Range Covering Elements from K Lists」類(情境與敘述為本平台改寫)。
輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了