AI & Data Dreamers練功房
寶箱片場規則
ALGO GATES・演算法關卡・高階・3 題

演算法高階・堆積與優先佇列

單一 worker 的排程、滑動視窗中位數、多來源日誌對齊的最小時間窗。

這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。

  1. 01

    單一 worker 的短任務優先

    困難堆積

    一台只有單一 worker 的機器處理排入的任務。每個任務有編號、排入時間與執行時間。規則:

    1. worker 閒著時,從「已排入(排入時間 ≤ 目前時間)而且還沒執行」的任務裡,挑執行時間最短的;一樣短挑編號小的
    2. 開始後就做到完成,中間不換手;完成的那一刻就能挑下一個
    3. 閒著而且沒有已排入的任務時,時間直接跳到下一個任務排入的時間

    一開始的時間是 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 執行,只用標準函式庫。

    作答登入後可作答
  2. 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 執行,只用標準函式庫。

    作答登入後可作答
  3. 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 執行,只用標準函式庫。

    作答登入後可作答