5660. 最多可以参加的会议数目 II
/*
先对events 进行排序，按照结束时间升序，如果一样则按照开始时间升序
dp[i][j] 代表以第j个会议结束，并且开i个会的最大和。
dp[0][j]=0
dp[i][j] = value[j] + max(dp[i-1][x]) (end[x]<=start[i]) preMax[x]去保存
best = max(dp[k][0...n])
1 <= valuei <= 10^6 , 1 <= k * events.length <= 10^6 可以得出结果不会超出int32
*/
func max(a, b int) int {
if a>b{return a}
return b
}
func GetPreMax(nums []int) []int {
preMax := make([]int, len(nums))
for key, value := range nums {
if key==0{
preMax[key]=value
}else {
preMax[key] = max(preMax[key-1], value)
}
}
return preMax
}
func findPreInd(events [][]int, i int) int {
for j:=i-1;j>=0;j-- {
if events[j][1]<events[i][0] {
return j
}
}
return -1
}
func maxValue(events [][]int, k int) int {
sort.Slice(events, func(i, j int) bool {
if events[i][1]<events[j][1]{return true}
if events[i][1]>events[j][1]{return false}
return events[i][0]<=events[j][0]
})
dp := make([][]int, k+1)
dp[0] = make([]int, len(events))
for i:=1;i<=k;i++ {
dp[i] = make([]int, len(events))
preMax:=GetPreMax(dp[i-1])
for j:=0;j<len(events);j++ {
dp[i][j] = events[j][2]
preInd := findPreInd(events, j)
if preInd>=0 {
dp[i][j] += preMax[preInd]
}
}
}
best :=0
for _, value := range dp[k] {
best = max(best, value)
}
return best
}