特地拎出來的總結
這篇總結不太一樣，為了紀念和我爸喋喋不休吵了近3h的時間和教訓，用Deepseek共同完成 ：
題目
T674176 T2-任務task
題目描述
時間限制： 2.0 秒
空間限制： 512 MiB
有 \(n\) 個任務，第 \(i\) 個任務需要占據 \([l_i,r_i]\) 的時間，每個任務都會在瞬間結束，不會干擾到之后的任務。
你需要保證只使用 \(k\) 條并行線路完成任務，具體來說：
在選擇任務后，你有 \(k\) 個流水線，第 \(t\) 流水線能分配若干任務 \([l_{t,i},r_{t,i}]\)。
合法方案需要滿足 \(l_{t,i+1}\ge r_{t,i}\)，即結束時間不能超過下一個開始時間，且所有任務都分配進去。
也就是說：
- 對于區間 \([1,2],[2,3]\)，可以分配到一條流水線上；
- 對于全部是 \([1,1]\) 區間的任務，都可以將其安排在一條流水線上；
- 但是如果是 \([2,2]\) 和 \([1,3]\) 兩個區間就無法安排在一條流水線上。
輸入格式
從標準輸入讀入數據。
第一行兩個正整數 \(n,k\)，表示任務的數量和同時最多能做的任務數。
接下來 \(n\) 行，第 \(i+1\) 行兩個整數表示 \(l_i,r_i\)。
輸出格式
輸出到標準輸出。
輸出一行一個整數，表示最多能完成的任務數。
輸入輸出樣例 #1
輸入 #1
3 1
1 2
2 3
1 3
輸出 #1
2
說明/提示
補充樣例0輸入
3 1
1 1
1 1
1 1
樣例0輸出
3
樣例1解釋
做任務 \(1\) 和任務 \(2\)。注意任務 \(1\) 結束的那一刻不算正在做任務 \(1\)，可以立即開始任務 \(2\)。
對于所有的數據，1 ≤ k ≤n ≤ 10?, 0 ≤ l? ≤ r? ≤ n
子任務
| 測試點編號 | \(n\leq\) | 特殊性質 |
|---|---|---|
| \(1\sim 3\) | \(17\) | \(k=1\) |
| \(4\sim 6\) | \(17\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(7\sim 13\) | \(17\) | 無特殊性質 |
| \(14\sim 16\) | \(10^2\) | \(k=1\) |
| \(17\sim 19\) | \(10^2\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(20\sim 25\) | \(10^2\) | 無特殊性質 |
| \(26\sim 28\) | \(5\times 10^3\) | \(k=1\) |
| \(29\sim 30\) | \(5\times 10^3\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(31\sim 41\) | \(5\times 10^3\) | 無特殊性質 |
| \(42\sim 43\) | \(5\times 10^4\) | \(k=1\) |
| \(44\sim 46\) | \(5\times 10^4\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(47\sim 55\) | \(5\times 10^4\) | 無特殊性質 |
| \(56\sim 58\) | \(10^5\) | \(k=1\) |
| \(59\sim 64\) | \(10^5\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(65\sim 76\) | \(10^5\) | \(r_i-l_i<10\) |
| \(77\sim 83\) | \(10^5\) | 無特殊性質 |
| \(84\sim 90\) | \(10^6\) | \(r_i-l_i<10\) |
| \(91\sim 92\) | \(10^6\) | \(k=1\) |
| \(93\sim 94\) | \(10^6\) | \(l_i\leq l_{i+1}\)，\(r_i\leq r_{i+1}\) |
| \(95\sim 100\) | \(10^6\) | 無特殊性質 |
題目關鍵點
- 問題本質：選擇盡可能多的任務，使得在任何時刻最多有 ( k ) 個任務同時進行（任務在結束時刻不計入進行中）。
- 核心約束：任務的時間區間 ([l_i, r_i]) 不能重疊超過 ( k ) 個，但允許任務在結束時刻立即開始下一個任務（即區間端點不重疊不計入沖突）。
- 數據規模：( n \leq 10^6 )，需要高效算法。
正解思路
題解中提到的正確解決方案是：
- 排序策略：將任務按照結束時間 ( r_i ) 從早到晚排序。這有助于優先安排結束早的任務，為后續任務留出空間。
- 貪心選擇：依次考慮每個任務，如果加入后不違反“任何時刻最多 ( k ) 個任務”的約束，則選擇該任務。
- 約束檢查：檢查加入任務后，任務區間 ([l_i, r_i]) 內的同時任務數是否超過 ( k )。這需要動態維護每個時間點的任務數。
- 數據結構優化：使用線段樹或堆來高效查詢區間最大值和更新任務數。具體來說：
- 線段樹：維護時間軸上的任務數，支持區間查詢最大值和區間加操作（當加入任務時，將 ([l_i, r_i]) 的任務數加1）。
- 堆優化：由于只需要檢查后綴最大值，可以用堆來維護當前進行中的任務結束時間，每次檢查時彈出已結束的任務。
正解的時間復雜度為 ( O(n \log n) ) 或 ( O(n \log C) )（其中 ( C ) 是時間范圍），能夠處理 ( n \leq 10^6 ) 的數據。
做題情況分析
- 暴力解法：最初實現了 ( O(n^2) ) 的暴力解法，即枚舉任務組合并檢查約束。這種方法在 ( n ) 較大時（如 ( n > 10^4 )）會超時，無法通過所有測試點。
- 問題根源：對 ( k ) 的特殊性不敏感，沒有意識到 ( k ) 可以作為優化關鍵。在暴力解法中，未能將問題轉化為貪心選擇與數據結構維護，導致無法優化到正解。
- 具體不足：
- 沒有使用排序策略來簡化問題。
- 沒有利用數據結構高效檢查區間任務數，而是每次重新計算，造成高復雜度。
- 忽略了題解中提到的“結束時間排序”和“區間查詢”的提示。
改進建議
- 轉換思路：對于區間選擇問題，優先考慮按結束時間排序的貪心策略，這常用于解決區間不重疊或資源限制問題。
- 利用 k 值：當 ( k ) 較小時，可以考慮更簡單的優化；但即使 ( k ) 較大，也應使用數據結構維護全局約束。
- 掌握數據結構：熟練運用線段樹、堆等數據結構處理區間查詢和更新，這是解決大規模數據問題的關鍵。
- 代碼實踐：在實現正解時，注意離散化時間點以降低空間復雜度，并小心處理區間端點（如結束時刻不計入）。
通過本題，應加強貪心算法與數據結構的結合應用，避免陷入暴力枚舉的思維定式。在類似問題中，及時分析約束條件并選擇高效算法是得分的關鍵。
浙公網安備 33010602011771號