難度: Hard
目前下列解法的時間複雜度: O(n*k*lg(n)) , 能不能把lg壓掉我不知道
題目說明
給你n個一維區間(兩端點都包含),每個區間有個分數。
及一個整數k。
求區間不重疊的情況下,選取最多k個區間,最高的分數總合是多少?
解法: dp
(在這天之前,選過幾個區間了) -> 得到的分數
更新時:
1. 從最小天數(端點)跑到最大天數(端點)
2. 式著選取將這天開始的區間,(區間右端+1,選過幾個區間了+1) <-選大- (這天,選過幾個區間了) + 這個區間的分數
3. 跑完表後拿 (最大天數+1,k) 回傳
唯一的問題是數字很大,要弄一個轉換方式
我是用一張表+二分搜查詢,不知道是不是這樣跑得很慢
source code