前往
大廳
主題

[leetcode]1751. Maximum Number of Events That Can Be Attended II

♙♲⚙\~O_O~/⚙♲♙ | 2021-07-29 12:00:05 | 巴幣 4 | 人氣 159

題目: 1751. Maximum Number of Events That Can Be Attended II
難度: Hard
目前下列解法的時間複雜度: O(n*k*lg(n)) , 能不能把lg壓掉我不知道


題目說明

給你n個一維區間(兩端點都包含),每個區間有個分數。
及一個整數k。
求區間不重疊的情況下,選取最多k個區間,最高的分數總合是多少?


解法: dp

(在這天之前,選過幾個區間了) -> 得到的分數
更新時:
1. 從最小天數(端點)跑到最大天數(端點)
2. 式著選取將這天開始的區間,(區間右端+1,選過幾個區間了+1) <-選大- (這天,選過幾個區間了) + 這個區間的分數
3. 跑完表後拿 (最大天數+1,k) 回傳

唯一的問題是數字很大,要弄一個轉換方式
我是用一張表+二分搜查詢,不知道是不是這樣跑得很慢


source code

然後我送這題一樣答案,執行時間會飄

創作回應

相關創作

更多創作