Maximum Earnings From Taxi (LeetCode 2008)

Nguồn: LeetCode 2008 Độ khó: Trung bình Quy hoạch động QHĐ tuyến tính

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

LeetCode 2008 – Maximum Earnings From Taxi (Thu nhập lớn nhất từ taxi) – độ khó Medium.

Có $n$ điểm trên con đường mà bạn đang lái taxi. $n$ điểm trên đường được đánh số từ $1$ đến $n$ theo hướng bạn đang đi, và bạn muốn lái từ điểm $1$ đến điểm $n$ để kiếm tiền bằng cách đón khách. Bạn không thể đổi hướng đi của taxi.

Các hành khách được biểu diễn bằng mảng số nguyên hai chiều rides đánh số từ 0, trong đó rides[i] = [starti, endi, tipi] cho biết hành khách thứ $i$ muốn đi từ điểm starti tới điểm endi và sẵn sàng boa tipi đô la.

Với mỗi hành khách $i$ mà bạn chở, bạn kiếm được endi - starti + tipi đô la. Tại mỗi thời điểm bạn chỉ được chở nhiều nhất một hành khách.

Cho $n$ và rides, hãy trả về số tiền lớn nhất bạn có thể kiếm được nếu chọn đón khách một cách tối ưu.

Lưu ý: bạn có thể trả một hành khách và đón một hành khách khác tại cùng một điểm.

Ví dụ 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7

Giải thích: ta có thể đón hành khách 0 để kiếm được 5 - 2 + 4 = 7 đô la.

Ví dụ 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20

Giải thích: ta sẽ đón các hành khách sau:

• Chở hành khách 1 từ điểm 3 tới điểm 10, lời 10 - 3 + 2 = 9 đô la.
• Chở hành khách 2 từ điểm 10 tới điểm 12, lời 12 - 10 + 3 = 5 đô la.
• Chở hành khách 5 từ điểm 13 tới điểm 18, lời 18 - 13 + 1 = 6 đô la.

Tổng cộng kiếm được 9 + 5 + 6 = 20 đô la.

Ràng buộc:

• $1 \le n \le 10^5$
• $1 \le$ rides.length $\le 3 \cdot 10^4$
• rides[i].length == 3
• $1 \le$ starti $\lt$ endi $\le n$
• $1 \le$ tipi $\le 10^5$

2008. Maximum Earnings From Taxi – Medium.

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi who is willing to give a tipi dollar tip.

For each passenger i you pick up, you earn endi - starti + tipi dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

Constraints:

• 1 <= n <= 10^5
• 1 <= rides.length <= 3 * 10^4
• rides[i].length == 3
• 1 <= starti < endi <= n
• 1 <= tipi <= 10^5

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Tóm tắt đề bài: có $N$ điểm trên đường được đánh số từ $1$ tới $N$, tài xế taxi chỉ đi một lèo từ điểm $1$ đến điểm $N$. Có một số hành khách, hành khách thứ $i$ yêu cầu được chở từ điểm start[i] đến end[i] và khi chở xong anh ta sẽ cho thêm tiền tip là tip[i]. Như vậy tiền tài xế nhận được nếu chở hành khách thứ $i$ là end[i] - start[i] + tip[i]. Tài xế luôn chạy từ $1$ đến $N$ và không bao giờ vòng ngược lại, nên nếu đã lỡ bỏ qua hành khách nào thì sẽ không quay lại đón người đó. Một xe taxi chỉ chở được nhiều nhất 1 hành khách. Hãy giúp tài xế chọn những hành khách nào để tổng tiền là lớn nhất.

Ví dụ 1: hai khách $[2, 5, 4]$ và $[1, 5, 1]$ chồng lên nhau (cùng cần xe trên đoạn 2 → 5) nên chỉ chở được 1 người. Chở khách 0 được $5 - 2 + 4 = 7$, chở khách 1 được $5 - 1 + 1 = 5$ ⇒ đáp án 7. Ví dụ 2 thì khách 1 trả ở điểm 10 và khách 2 đón ở đúng điểm 10 – được phép theo lưu ý của đề.

Về dữ liệu vào / ra của code trong bài

Trên LeetCode các bạn chỉ cần nộp phần class Solution (cùng các mảng toàn cục phía trên). Để các bạn chạy thử được trên máy (hoặc trang Chạy code online), code trong bài có thêm hàm main đọc từ bàn phím: dòng đầu là $n$ và $m$ (số hành khách), $m$ dòng sau mỗi dòng 3 số start end tip; in ra số tiền lớn nhất. Ví dụ 1 sẽ nhập là:

5 2
2 5 4
1 5 1

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào để nhảy tới:

Cách 1Quy hoạch động theo điểm trả khách · O(N + M)

Cách 1Quy hoạch động theo điểm trả khách – O(N + M)

Phương pháp giải: quy hoạch động.

Chuẩn bị: gom các khách theo điểm xuống xe

Với mỗi điểm $i$, ta lưu một danh sách save[i] là các hành khách $j$ yêu cầu được chở và đáp xuống tại điểm $i$ (tức end[j] = i).

Công thức quy hoạch động

• Gọi f[i] (trong code là dp[i]) là tổng tiền lớn nhất kiếm được khi ta đi đến điểm thứ $i$ trên đường.
• Bài toán cơ sở: f[0] = 0.
• Nếu tại điểm thứ $i$ không có khách nào xuống (hoặc ta không chở ai kết thúc ở đây) thì f[i] = f[i - 1].
• Nếu ta quyết định chở một hành khách $j$ nào đó kết thúc tại điểm $i$ (end[j] = i), thì trước khi đón người này, ta phải đang rảnh tại điểm start[j], với số tiền lớn nhất tích luỹ được tới đó là f[start[j]]. Tức f[i] = f[start[j]] + end[j] - start[j] + tip[j].
• Kết quả: f[n].

Công thức

$f[i] = \max\Big(f[i-1],\ \max\limits_{j:\ end_j = i} \big(f[start_j] + end_j - start_j + tip_j\big)\Big)$, $\ f[0] = 0$, đáp án $f[n]$.

Vì sao dùng f[start[j]] là đủ?

f[start[j]] đã là số tiền lớn nhất với mọi cách chọn khách mà xuống xe không muộn hơn điểm start[j]. Những khách đó không chồng lên chuyến của khách $j$ (vì đề cho phép trả khách và đón khách mới tại cùng một điểm). Do ta tính $f$ theo thứ tự $i$ tăng dần và start[j] < end[j] = i nên khi cần thì f[start[j]] đã được tính xong.

Đánh giá độ phức tạp: $O(N)$ – chính xác hơn là $O(N + M)$ vì mỗi khách chỉ được xét đúng 1 lần (tại điểm xuống xe của họ).

Minh hoạ bảng quy hoạch động

Em nhập $n$ và các chuyến (mỗi chuyến 3 số start end tip, các chuyến cách nhau dấu ;) rồi bấm Tiếp. Mỗi thanh ngang là một hành khách; cột cam là điểm $i$ đang tính, cột xanh là điểm start của chuyến đang xét:

n rides

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

long long dp[100005];
vector <int> save[100005];
class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
        for (int i = 0; i <= 100000; i++) {
            save[i].clear();
            dp[i] = -1;
        }
        for (int i = 0; i < (int) rides.size(); i++) {
            save[rides[i][1]].push_back(i);
        }
        dp[0] = 0;
        long long res = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = max(dp[i], dp[i - 1]);
            for (int j = 0; j < (int) save[i].size(); j++) {
                vector <int> taxi = rides[save[i][j]];
                dp[i] = max(dp[i], dp[taxi[0]] + taxi[1] - taxi[0] + taxi[2]);
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> rides(m, vector<int>(3));
    for (int i = 0; i < m; i++) cin >> rides[i][0] >> rides[i][1] >> rides[i][2];
    Solution sol;
    cout << sol.maxTaxiEarnings(n, rides);
    return 0;
}

import sys
from typing import List

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        save = [[] for _ in range(n + 1)]   # save[i]: các chuyến kết thúc tại điểm i
        for j, r in enumerate(rides):
            save[r[1]].append(j)
        dp = [0] * (n + 1)
        res = 0
        for i in range(1, n + 1):
            dp[i] = dp[i - 1]               # bỏ qua điểm i
            for j in save[i]:
                s, e, tip = rides[j]
                dp[i] = max(dp[i], dp[s] + e - s + tip)
            res = max(res, dp[i])
        return res

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    rides = [[int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])] for i in range(m)]
    print(Solution().maxTaxiEarnings(n, rides))

main()

Một vài chỗ cần để ý trong code:

1. Các mảng dp, save khai báo toàn cục, LeetCode chạy nhiều test trên cùng một chương trình nên đầu hàm phải clear và gán lại hết. Mình gán dp[i] = -1 ban đầu rồi dp[0] = 0; vì mọi dp[i] đều lấy max với dp[i - 1] ≥ 0 nên giá trị $-1$ không bao giờ lọt ra kết quả.
2. res lấy max của mọi dp[i], thực ra chính bằng dp[n] vì $dp$ không giảm. Bản Python mình gán thẳng dp[i] = dp[i - 1] cho gọn, ý tưởng y hệt.
3. vector <int> taxi = rides[...] sao chép 3 số của chuyến ra cho dễ đọc, chỉ tốn hằng số.

Nhớ dùng long long

Đáp án có thể vượt quá giới hạn int: ví dụ $3 \cdot 10^4$ chuyến nối tiếp nhau, mỗi chuyến tip $10^5$ ⇒ tổng hơn $3 \cdot 10^9$. Vì vậy hàm trả về long long và mảng dp cũng là long long.

Em có thể chạy tay từng dòng code C++ ở khung dưới đây:

C++▶ Chạy tay từng dòng codedp[i] = max(dp[i-1], dp[start] + end - start + tip) với mọi khách xuống tại i.

Dữ liệu vào (stdin) – sửa thoải mái5 2 2 5 4 1 5 1

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long dp[100005];

5vector <int> save[100005];

6class Solution {

7public:

8 long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {

9 for (int i = 0; i <= 100000; i++) {

10 save[i].clear();

11 dp[i] = -1;

12 }

13 for (int i = 0; i < (int) rides.size(); i++) {

14 save[rides[i][1]].push_back(i);

15 }

16 dp[0] = 0;

17 long long res = 0;

18 for (int i = 1; i <= n; i++) {

19 dp[i] = max(dp[i], dp[i - 1]);

20 for (int j = 0; j < (int) save[i].size(); j++) {

21 vector <int> taxi = rides[save[i][j]];

22 dp[i] = max(dp[i], dp[taxi[0]] + taxi[1] - taxi[0] + taxi[2]);

23 }

24 res = max(res, dp[i]);

25 }

26 return res;

27 }

28};

29

30int main() {

31 int n, m;

32 cin >> n >> m;

33 vector<vector<int>> rides(m, vector<int>(3));

34 for (int i = 0; i < m; i++) cin >> rides[i][0] >> rides[i][1] >> rides[i][2];

35 Solution sol;

36 cout << sol.maxTaxiEarnings(n, rides);

37 return 0;

38}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Thời gian: vòng lặp chính chạy $N$ lần, mỗi khách được xét đúng 1 lần tại điểm xuống của họ ⇒ $O(N + M)$ (cộng thêm $10^5$ bước khởi tạo mảng toàn cục).
• Không gian: mảng dp và save ⇒ $O(N + M)$.

Không gian$O(N + M)$

Thời gian$O(N + M)$

Ghi chú của mình: code C++ và Python ở trên chạy đúng 2 ví dụ của đề, và được kiểm tra với 500 bộ test ngẫu nhiên nhỏ, so với code vét cạn thử mọi tập khách không chồng nhau – khớp hết. Với $n = 10^5$, $3 \cdot 10^4$ chuyến: C++ chạy khoảng 0.03 giây, Python khoảng 0.1 giây; test $3 \cdot 10^4$ chuyến nối tiếp tip $10^5$ cho đáp án $3\,000\,030\,000$ (vượt int) – cả hai bản đều đúng.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇