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

演算法高階・區間與掃描線

事件排序後掃一遍:CPU 超用時段、最少補跑批次、限流上限的變化點。

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

  1. 01

    叢集 CPU 超用時段

    困難掃描線

    叢集的 CPU 配額是 C 核。每個工作在時間區間 [開始, 結束) 內佔用固定的核數(結束那一刻已釋放)。請找出 CPU 用量的尖峰,以及用量超過 C 的所有時段。

    輸入:

    第 1 行:配額 C

    第 2 行:工作數 n

    接下來 n 行:工作名 開始 結束 核數(整數,開始 < 結束)

    輸出:兩行

    第 1 行:PEAK 尖峰核數 AT 時間:時間是第一次達到尖峰的時刻

    第 2 行:用量嚴格大於 C 的時段,以 開始-結束 表示、依時間排序、以空白分隔;相連的時段要合併成一段(例如 [10,20) 與 [20,30) 合併成 10-30);沒有超用印 NONE

    要求:把每個工作拆成「開始時 +核數、結束時 −核數」兩個事件,依時間排序後掃一遍;同一時刻的事件全部套用後才計算用量。不要逐一時間單位模擬(時間是秒級的大整數)。

    範例輸入:

    8

    4

    j1 0 50 5

    j2 20 60 4

    j3 50 90 3

    j4 60 70 6

    範例輸出:

    PEAK 9 AT 20

    20-50 60-70

    類型對應:LeetCode「Car Pooling」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答
  2. 02

    最少補跑批次覆蓋全天

    困難區間/貪婪

    某天的資料有缺口,要用補跑批次把 [0, T) 這段時間全部重新覆蓋。可用的補跑批次各自涵蓋 [開始, 結束),批次之間可以重疊。請用最少的批次數把 [0, T) 完全蓋住。

    輸入:

    第 1 行:組數 t

    接下來 t 行:T 開始-結束 開始-結束 ...(整數,開始 < 結束,至少一個批次)

    輸出:每組一行

    • 蓋得住:印最少的批次數
    • 蓋不住:印 GAP x,x 是從 0 開始往後,第一個沒有任何批次蓋到的時間點

    要求:依開始時間排序後貪婪:每一步在「開始時間 ≤ 目前已覆蓋到的位置」的批次裡,選結束時間最遠的。不要列舉批次的組合。

    範例輸入:

    2

    10 0-4 3-7 6-10 2-5

    8 0-3 4-8

    範例輸出:

    3

    GAP 3

    類型對應:LeetCode「Video Stitching」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答
  3. 03

    限流上限的變化點

    困難掃描線/堆積

    API 閘道設了多條限流規則,每條規則在 [生效, 失效) 期間內允許每秒 r 次請求。同一時間有多條規則生效時,以上限最高的那條為準;沒有規則生效時上限是 0。請列出「實際上限」改變的所有時間點。

    輸入:

    第 1 行:規則數 n

    接下來 n 行:規則名 生效 失效 r(整數,生效 < 失效,r > 0)

    輸出:每個變化點一行 時間 新上限,依時間排序。只在實際上限和前一刻不同時才印(從上限 0 開始比;同一時刻有多條規則開始或結束,以該時刻全部套用後的結果為準)。

    要求:把所有生效、失效時刻排序後掃描,用 heap 存 (−r, 失效時間) 取目前最高的上限,過期的規則在堆頂時才移除(延遲刪除)。不要逐秒模擬。

    範例輸入:

    3

    a 0 10 5

    b 2 6 8

    c 6 12 5

    範例輸出:

    0 5

    2 8

    6 5

    12 0

    類型對應:LeetCode「The Skyline Problem」類(情境與敘述為本平台改寫)。

    輸入請用 input() 逐行讀取(平台不支援 sys.stdin)。執行時平台會把每一行測資回顯在輸出最前面,這是正常的,不用自己印。starter 已先把全部輸入讀進來,請保留這段,不要在迴圈裡邊讀邊印(回顯行會插進輸出中間,就對不上答案)。本題在瀏覽器內以 Pyodide 執行,只用標準函式庫。

    作答登入後可作答