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

演算法中階・區間與貪婪

排序後每一步做當下最好的選擇:排程衝突、資源配對、日誌切段。

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

  1. 01

    最少取消幾個排程

    中等區間/貪婪

    同一台資料庫一次只能跑一個維護工作。每個工作占用的時段是 [開始, 結束):結束時間等於另一個工作的開始時間不算衝突。為了讓剩下的工作彼此都不衝突,最少要取消幾個工作?

    輸入:

    第 1 行:工作數 n

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

    輸出:一行,最少要取消的工作數。

    要求:用貪婪法,不要試所有取捨組合。

    範例輸入:

    4

    j1 1 3

    j2 2 4

    j3 3 5

    j4 1 3

    範例輸出:

    2

    類型對應:LeetCode「Non-overlapping Intervals」類(情境與敘述為本平台改寫)。

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

    作答登入後可作答
  2. 02

    依記憶體分派任務

    中等貪婪

    有一批任務與一批 worker。每個任務需要至少 m GB 記憶體,每個 worker 有 c GB 記憶體,只有 c ≥ m 時那個 worker 才能跑這個任務。每個 worker 最多跑一個任務,每個任務最多派給一個 worker。最多能同時跑幾個任務?

    輸入:

    第 1 行:每個任務需要的記憶體(整數,以空白分隔)

    第 2 行:每個 worker 的記憶體(整數,以空白分隔)

    輸出:兩行

    第 1 行:最多能同時跑的任務數

    第 2 行:沒被派到任務的 worker 數

    要求:排序後用貪婪法配對,不要試所有配對方式。

    範例輸入:

    4 1 6

    2 5 1

    範例輸出:

    2

    1

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

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

    作答登入後可作答
  3. 03

    依使用者切分日誌分段

    中等貪婪

    要把一段點擊日誌切成連續的幾段,分給不同的 worker 平行處理。為了讓每個使用者的工作階段完整留在同一個 worker,同一個 user_id 只能出現在其中一段。在這個條件下,請切出最多段。

    輸入:一行,依時間順序的 user_id,以空白分隔(至少一筆)

    輸出:兩行

    第 1 行:最多能切成幾段

    第 2 行:每一段的筆數,依先後順序以空白分隔

    要求:先記下每個 user_id 最後出現的位置,再走一次就決定切點。

    範例輸入:

    a b a c d c e

    範例輸出:

    3

    3 3 1

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

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

    作答登入後可作答