演算法中階・區間與貪婪
排序後每一步做當下最好的選擇:排程衝突、資源配對、日誌切段。
這一頁是題幹試閱;登入/註冊後每題可以在瀏覽器裡執行、對答案,第一次交對 +10 XP。
- 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 執行,只用標準函式庫。
作答登入後可作答 - 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 執行,只用標準函式庫。
作答登入後可作答 - 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 執行,只用標準函式庫。
作答登入後可作答

送件鴿飛出去了