1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func maxTaxiEarnings(n int, rides [][]int) int64 {
sort.Slice(rides, func (i, j int) bool {
return rides[i][1] < rides[j][1]
})
dp := make([]int64, len(rides) + 1)
for i, ride := range rides {
start := ride[0]
end := ride[1]
tip := ride[2]
j := halfSearch(rides, i, start)
dp[i + 1] = max(dp[i], dp[j] + int64(end - start + tip))
}
return dp[len(rides)]
}
func halfSearch(rides [][]int, right, target int) int {
left := 0
for left <= right {
mid := ((right - left + 1) >> 1) + left
if rides[mid][1] <= target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
|
