你驾驶出租车行驶在一条有 n 个地点的路上。这 n 个地点从近到远编号为 1 到 n ,你想要从 1 开到 n ,通过接乘客订单盈利。
你只能沿着编号递增的方向前进,不能改变方向。
乘客信息用一个下标从 0 开始的二维数组 rides 表示,
其中 rides[i] = [starti, endi, tipi] 表示第 i 位乘客需要从地点 starti 前往 endi ,愿意支付 tipi 元的小费。
每一位 你选择接单的乘客 i ,你可以 盈利 endi - starti + tipi 元。你同时 最多 只能接一个订单。
给你 n 和 rides ,请你返回在最优接单方案下,你能盈利 最多 多少元。
注意:你可以在一个地点放下一位乘客,并在同一个地点接上另一位乘客。
示例 1:输入:n = 5, rides = [[2,5,4],[1,5,1]] 输出:7
解释:我们可以接乘客 0 的订单,获得 5 - 2 + 4 = 7 元。
示例 2:输入:n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]] 输出:20
解释:我们可以接以下乘客的订单:
- 将乘客 1 从地点 3 送往地点 10 ,获得 10 - 3 + 2 = 9 元。
- 将乘客 2 从地点 10 送往地点 12 ,获得 12 - 10 + 3 = 5 元。
- 将乘客 5 从地点 13 送往地点 18 ,获得 18 - 13 + 1 = 6 元。
我们总共获得 9 + 5 + 6 = 20 元。
提示:1 <= n <= 105
1 <= rides.length <= 3 * 104
rides[i].length == 3
1 <= starti < endi <= n
1 <= tipi <= 105
1、动态规划+二分查找+内置函数;时间复杂度O(nlog(n)),空间复杂度O(n)
func maxTaxiEarnings(n int, rides [][]int) int64 {
m := len(rides)
arr := make([][]int64, 0)
for i := 0; i < m; i++ {
a, b, c := rides[i][0], rides[i][1], rides[i][2]
arr = append(arr, []int64{int64(a), int64(b), int64(b - a + c)})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] < arr[j][0]
}
return arr[i][1] < arr[j][1]
})
for i := 1; i < m; i++ {
target := sort.Search(i, func(j int) bool {
return arr[j][1] > arr[i][0]
})
if target == 0 {
arr[i][2] = max(arr[i][2], arr[i-1][2])
} else {
arr[i][2] = max(arr[i][2]+arr[target-1][2], arr[i-1][2])
}
}
return arr[m-1][2]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
2、动态规划+二分查找;时间复杂度O(nlog(n)),空间复杂度O(n)
func maxTaxiEarnings(n int, rides [][]int) int64 {
m := len(rides)
arr := make([][]int64, 0)
for i := 0; i < m; i++ {
a, b, c := rides[i][0], rides[i][1], rides[i][2]
arr = append(arr, []int64{int64(a), int64(b), int64(b - a + c)})
}
sort.Slice(arr, func(i, j int) bool {
if arr[i][1] == arr[j][1] {
return arr[i][0] < arr[j][0]
}
return arr[i][1] < arr[j][1]
})
dp := make([]int64, m)
dp[0] = arr[0][2]
for i := 1; i < m; i++ {
left, right := 0, i-1
for left < right {
mid := left + (right-left)/2
if arr[mid+1][1] <= arr[i][0] {
left = mid + 1
} else {
right = mid
}
}
if arr[left][1] <= arr[i][0] {
dp[i] = max(dp[i-1], dp[left]+arr[i][2])
} else {
dp[i] = max(dp[i-1], arr[i][2])
}
}
return dp[m-1]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
3、动态规划;时间复杂度O(n),空间复杂度O(n)
func maxTaxiEarnings(n int, rides [][]int) int64 {
dp := make([]int, n+1) // dp[i]到达i位置的最大盈利
arr := make([][][2]int, n+1)
for i := 0; i < len(rides); i++ {
a, b, c := rides[i][0], rides[i][1], rides[i][2]
arr[b] = append(arr[b], [2]int{a, b - a + c})
}
for i := 1; i <= n; i++ {
dp[i] = dp[i-1]
for j := 0; j < len(arr[i]); j++ {
a, c := arr[i][j][0], arr[i][j][1]
dp[i] = max(dp[i], dp[a]+c)
}
}
return int64(dp[n])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
4、动态规划;时间复杂度O(n),空间复杂度O(n)
func maxTaxiEarnings(n int, rides [][]int) int64 {
dp := make([]int, n+1) // dp[i]到达i位置的最大盈利
sort.Slice(rides, func(i, j int) bool {
if rides[i][0] == rides[j][0] {
return rides[i][1] < rides[j][1]
}
return rides[i][0] < rides[j][0]
})
j := 1
for i := 0; i < len(rides); i++ { // 遍历订单
a, b, c := rides[i][0], rides[i][1], rides[i][2]
for j < a { // 更新指针
j++
dp[j] = max(dp[j], dp[j-1])
}
dp[b] = max(dp[b], dp[j]+(b-a+c))
}
for ; j <= n; j++ {
dp[j] = max(dp[j], dp[j-1])
}
return int64(dp[n])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
Medium题目,动态规划题目,题目基本同leetcode 1235.规划兼职工作;长度n范围小,可以以n为维度展开动态规划,也可以以订单为维度展开动态规划
页面更新:2024-03-27
本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828
© CopyRight 2020-2024 All Rights Reserved. Powered By 71396.com 闽ICP备11008920号-4
闽公网安备35020302034903号