2023-07-25：你駕駛出租車行駛在一條有 n 個地點的路上
<bdo id='23ll0'></bdo><ul id='23ll0'></ul>
這 n 個地點從近到遠編號為 1 到 n ，你想要從 1 開到 n
通過接乘客訂單盈利。你只能沿著編號遞增的方向前進，不能改變方向
乘客信息用一個下標從 0 開始的二維數組 rides 表示
其中 rides[i] = [starti, endi, tipi]
表示第 i 位乘客需要從地點 starti 前往 endi
愿意支付 tipi 元的小費
每一位 你選擇接單的乘客 i ，你可以 盈利 endi - starti + tipi 元
你同時 最多 只能接一個訂單。
給你 n 和 rides ，請你返回在最優接單方案下，你能盈利 最多 多少元。
注意：你可以在一個地點放下一位乘客，并在同一個地點接上另一位乘客。
輸入：n = 5, rides = [[2,5,4],[1,5,1]]。
輸出：7。
答案2023-07-25：
maxTaxiEarnings1算法的大體過程如下：
1.對乘客訂單rides按照起始地點的編號進行升序排序。
2.調用build函數，構建區間樹數據結構，初始化max數組。
3.遍歷排序后的rides數組，對每個乘客訂單進行處理：
a.根據乘客訂單的起始地點，通過maxQuery函數查詢當前位置之前的最大盈利額，存儲在money變量中。
b.計算當前乘客訂單的盈利額，即end-start+tip。
c.將當前乘客訂單的結束地點作為索引，更新max數組中對應位置的值，更新為money+當前乘客訂單的盈利額。
4.返回maxQuery函數查詢整個路程的最大盈利額，即maxQuery(n)。
maxTaxiEarnings2算法的大體過程如下：
1.初始化sorted數組，用于存儲所有乘客訂單的起始和結束地點，長度為乘客訂單數量的兩倍。
2.遍歷rides數組，將乘客訂單的起始和結束地點依次存儲到sorted數組中。
3.對sorted數組進行升序排序。
4.對乘客訂單rides按照起始地點的編號進行升序排序。
5.初始化dp數組，并將所有元素置為0。
6.初始化dpi變量為0，用于記錄當前處理到的sorted數組下標。
7.初始化pre和ans變量為0。
8.遍歷排序后的rides數組，對每個乘客訂單進行處理：
a.獲取當前乘客訂單的起始和結束地點。
b.分別使用rank函數查找sorted數組中起始和結束地點的下標。
c.更新dp數組，從dpi到起始地點的下標之間的元素，將其值更新為max(pre, dp[dpi])。
d.計算當前乘客訂單的盈利額，即end-start+tip。
e.更新ans變量，取盈利額和當前ans的最大值。
f.將dp數組中結束地點的下標位置的值更新為max(dp[erank], 盈利額)。
9.返回ans變量，即最大盈利額。
這兩種算法的核心思想都是通過動態規劃來計算每個乘客訂單的盈利額，并利用區間樹或排序數組來快速查詢之前的最大盈利額，從而得到整個路程的最大盈利額。
maxTaxiEarnings1算法的總的時間復雜度為O(nlogn)，總的額外空間復雜度為O(n)。
maxTaxiEarnings2算法的總的時間復雜度為O(nlogn)，總的額外空間復雜度為O(n)。
# go完整代碼如下：
```go
package main
import (
"fmt"
"sort"
)
const MAXN = 100001
var max = make([]int64, MAXN<<2)
var sorted = make([]int, MAXN)
var dp = make([]int64, MAXN)
var n = 0
func build(l, r, rt int) {
if l == r {
max[rt] = 0
} else {
mid := (l + r) / 2
build(l, mid, rt<<1)
build(mid+1, r, rt<<1|1)
pushUp(rt)
}
}
func maxQuery(r int) int64 {
if r < 1 {
return 0
}
return maxQueryRange(1, r, 1, n, 1)
}
func maxQueryRange(L, R, l, r, rt int) int64 {
if L <= l && r <= R {
return max[rt]
}
mid := (l + r) >> 1
ans := int64(0)
if L <= mid {
ans = max64(ans, maxQueryRange(L, R, l, mid, rt<<1))
}
if R > mid {
ans = max64(ans, maxQueryRange(L, R, mid+1, r, rt<<1|1))
}
return ans
}
func update(index int, c int64) {
updateNode(index, c, 1, n, 1)
}
func updateNode(index int, c int64, l, r, rt int) {
if l == r {
max[rt] = max64(max[rt], c)
} else {
mid := (l + r) >> 1
if index <= mid {
updateNode(index, c, l, mid, rt<<1)
} else {
updateNode(index, c, mid+1, r, rt<<1|1)
}
pushUp(rt)
}
}
func pushUp(rt int) {
max[rt] = max64(max[rt<<1], max[rt<<1|1])
}
func maxTaxiEarnings1(len int, rides [][]int) int64 {
sort.Slice(rides, func(i, j int) bool {
return rides[i][0] < rides[j][0]
})
n = len
build(1, n, 1)
for _, ride := range rides {
money := maxQuery(ride[0]) + int64(ride[1]-ride[0]+ride[2])
update(ride[1], money)
}
return maxQuery(n)
}
func rank(sorted []int, len int, num int) int {
ans := 0
l := 0
r := len - 1
for l <= r {
m := (l + r) / 2
if sorted[m] >= num {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}
func maxTaxiEarnings2(len0 int, rides [][]int) int64 {
m := len(rides)
j := 0
for i := 0; i < m; i++ {
sorted[j] = rides[i][0]
j++
sorted[j] = rides[i][1]
j++
}
sort.Slice(rides, func(i, j int) bool {
return rides[i][0] < rides[j][0]
})
sort.Ints(sorted[:m<<1])
for i := 0; i < m<<1; i++ {
dp[i] = 0
}
dpi := 0
pre := int64(0)
ans := int64(0)
for _, ride := range rides {
start := ride[0]
end := ride[1]
tips := ride[2]
srank := rank(sorted, m<<1, start)
erank := rank(sorted, m<<1, end)
for dpi <= srank {
pre = max64(pre, dp[dpi])
dpi++
}
money := pre + int64(end-start+tips)
ans = max64(money, ans)
dp[erank] = max64(dp[erank], money)
}
return ans
}
func max64(a, b int64) int64 {
if a > b {
return a
}
return b
}
func main() {
n := 5
rides := [][]int{{2, 5, 4}, {1, 5, 1}}
// n := 20
// rides := [][]int{{1, 6, 1}, {3, 10, 2}, {10, 12, 3}, {11, 12, 2}, {12, 15, 2}, {13, 18, 1}}
result1 := maxTaxiEarnings1(n, rides)
result2 := maxTaxiEarnings2(n, rides)
fmt.Println("Result from maxTaxiEarnings1:", result1)
fmt.Println("Result from maxTaxiEarnings2:", result2)
}
```
