2008. Maximum Earnings From Taxi (Medium)

start, end 구간과 구간 내 얻을 수 있는 profit이 주어짐

구간이 겹치지 않게 profit이 최대가 되도록 각 구간을 선택

 

for i in range(len(rides)):     rides[i][2] = rides[i][1] - rides[i][0] + rides[i][2] rides.sort(key=lambda p: p[1]) dp = [[0, 0]] for start, end, profit in rides:     idx = bisect.bisect_left(dp, [start + 1])     if dp[-1][1] < dp[idx - 1][1] + profit:         dp += [end, dp[idx - 1][1] + profit], return dp[-1][1]