2023-07-25：你駕駛出租車行駛在一條有 n 個(gè)地點(diǎn)的路上

這 n 個(gè)地點(diǎn)從近到遠(yuǎn)編號(hào)為 1 到 n ，你想要從 1 開到 n

通過(guò)接乘客訂單盈利。你只能沿著編號(hào)遞增的方向前進(jìn)，不能改變方向

乘客信息用一個(gè)下標(biāo)從 0 開始的二維數(shù)組 rides 表示

其中 rides[i] = [starti, endi, tipi]

表示第 i 位乘客需要從地點(diǎn) starti 前往 endi

愿意支付 tipi 元的小費(fèi)

每一位 你選擇接單的乘客 i ，你可以 盈利 endi - starti + tipi 元

你同時(shí) 最多 只能接一個(gè)訂單。

給你 n 和 rides ，請(qǐng)你返回在最優(yōu)接單方案下，你能盈利 最多 多少元。

注意：你可以在一個(gè)地點(diǎn)放下一位乘客，并在同一個(gè)地點(diǎn)接上另一位乘客。

輸入：n = 5, rides = [[2,5,4],[1,5,1]]。

輸出：7。

答案2023-07-25：

maxTaxiEarnings1算法的大體過(guò)程如下：

1.對(duì)乘客訂單rides按照起始地點(diǎn)的編號(hào)進(jìn)行升序排序。

2.調(diào)用build函數(shù)，構(gòu)建區(qū)間樹數(shù)據(jù)結(jié)構(gòu)，初始化max數(shù)組。

3.遍歷排序后的rides數(shù)組，對(duì)每個(gè)乘客訂單進(jìn)行處理：

a.根據(jù)乘客訂單的起始地點(diǎn)，通過(guò)maxQuery函數(shù)查詢當(dāng)前位置之前的最大盈利額，存儲(chǔ)在money變量中。

b.計(jì)算當(dāng)前乘客訂單的盈利額，即end-start+tip。

c.將當(dāng)前乘客訂單的結(jié)束地點(diǎn)作為索引，更新max數(shù)組中對(duì)應(yīng)位置的值，更新為money+當(dāng)前乘客訂單的盈利額。

4.返回maxQuery函數(shù)查詢整個(gè)路程的最大盈利額，即maxQuery(n)。

maxTaxiEarnings2算法的大體過(guò)程如下：

1.初始化sorted數(shù)組，用于存儲(chǔ)所有乘客訂單的起始和結(jié)束地點(diǎn)，長(zhǎng)度為乘客訂單數(shù)量的兩倍。

2.遍歷rides數(shù)組，將乘客訂單的起始和結(jié)束地點(diǎn)依次存儲(chǔ)到sorted數(shù)組中。

3.對(duì)sorted數(shù)組進(jìn)行升序排序。

4.對(duì)乘客訂單rides按照起始地點(diǎn)的編號(hào)進(jìn)行升序排序。

5.初始化dp數(shù)組，并將所有元素置為0。

6.初始化dpi變量為0，用于記錄當(dāng)前處理到的sorted數(shù)組下標(biāo)。

7.初始化pre和ans變量為0。

8.遍歷排序后的rides數(shù)組，對(duì)每個(gè)乘客訂單進(jìn)行處理：

a.獲取當(dāng)前乘客訂單的起始和結(jié)束地點(diǎn)。

b.分別使用rank函數(shù)查找sorted數(shù)組中起始和結(jié)束地點(diǎn)的下標(biāo)。

c.更新dp數(shù)組，從dpi到起始地點(diǎn)的下標(biāo)之間的元素，將其值更新為max(pre, dp[dpi])。

d.計(jì)算當(dāng)前乘客訂單的盈利額，即end-start+tip。

e.更新ans變量，取盈利額和當(dāng)前ans的最大值。

f.將dp數(shù)組中結(jié)束地點(diǎn)的下標(biāo)位置的值更新為max(dp[erank], 盈利額)。

9.返回ans變量，即最大盈利額。

這兩種算法的核心思想都是通過(guò)動(dòng)態(tài)規(guī)劃來(lái)計(jì)算每個(gè)乘客訂單的盈利額，并利用區(qū)間樹或排序數(shù)組來(lái)快速查詢之前的最大盈利額，從而得到整個(gè)路程的最大盈利額。

maxTaxiEarnings1算法的總的時(shí)間復(fù)雜度為O(nlogn)，總的額外空間復(fù)雜度為O(n)。

maxTaxiEarnings2算法的總的時(shí)間復(fù)雜度為O(nlogn)，總的額外空間復(fù)雜度為O(n)。

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)
}