[Leetcode] 1751. Maximum Number of Events That Can Be Attended II
initial
i saw a hint but its hard
firstly wtf is the dp formula? its 2d table but for each event i, we need to see if we can fill value up to j capacity.
formula is
dp[i][j]= either skip or take the current event and its value and move to the next valid event. Notice we need to find the next valid event and we can do o(n) linear search but we can do BS with log n. Once we find the valid index, we need to subtract the capacity.
dp[i][j]= max(dp[i+1][j], events[i][2]+dp[next_index][j-1])
Notice since we are searching for i+1th event, the dp table needs to be initalised as i+1. Also, we need to iterate reverse from length-1, not 0 cuz we are updating top->bottom.
since we are searching in reverse, the answer is stored in the 0th row and kth column
sol
class Solution:
def maxValue(self, events: List[List[int]], k: int) -> int:
length = len(events)
dp=[[0 for _ in range(k+1)] for _ in range(length+1)]
events.sort(key = lambda x:x[0])
def find(target):
left,right=0, len(events)
while left<right:
mid = left+(right-left)//2
if events[mid][0] <=target:
left=mid+1
else:
right=mid
return left
for i in range(length-1,-1,-1):
for j in range(k+1):
if j==0:
dp[i][j]=0
else:
end = events[i][1]
next_index = find(end)
take=events[i][2]
if next_index<length:
take+=dp[next_index][j-1]
dp[i][j]= max(dp[i+1][j], take)
return dp[0][k]
complexity
n log n sort + nk log n cuz iterating through nk
n*k space
