Activity Selection Problem

Q: Độ phức tạp thời gian của bài toán chọn hoạt động là gì?

Việc sắp xếp theo thời gian kết thúc tốn O(n log n) , còn lượt duyệt tham lam sau đó tốn O(n) , nên phần sắp xếp chi phối độ phức tạp. Nếu các hoạt động đã được sắp xếp theo thời gian kết thúc, chỉ cần lượt duyệt là có thể giải quyết bài toán trong thời gian O(n) và dùng thêm không gian O(1) .

DễTham lam Sắp xếp

+10

Hoạt động i diễn ra từ thời điểm start[i] đến thời điểm finish[i]. Một người chỉ thực hiện một hoạt động tại một thời điểm, và hoạt động tiếp theo phải bắt đầu sau khi hoạt động trước đó kết thúc: hoạt động bắt đầu đúng vào thời điểm một hoạt động khác kết thúc không thể diễn ra tiếp theo.

Trả về số lượng hoạt động lớn nhất mà một người có thể thực hiện.

Hàm

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: thời gian bắt đầu của mỗi hoạt động
finishinteger-array: thời điểm kết thúc của mỗi hoạt động; finish[i] tương ứng với start[i]
Trả vềinteger: số hoạt động nhiều nhất mà một người có thể thực hiện lần lượt

Ràng buộc

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
Một hoạt động có thể bắt đầu và kết thúc cùng lúc. Các mảng không được sắp xếp.

Ví dụ

Đầu vào: start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
Đầu ra: 4
Giải thích: Thực hiện các khoảng từ 10 đến 13, từ 14 đến 19, từ 21 đến 22 và từ 25 đến 30 sẽ được 4. Không thể đạt 5: khoảng từ 10 đến 13 xung đột với khoảng từ 12 đến 16, và khoảng từ 21 đến 22 xung đột với khoảng từ 20 đến 24.

Đầu vào: start = [1, 5, 9]finish = [5, 9, 12]
Đầu ra: 2
Giải thích: Hoạt động từ 5 đến 9 bắt đầu đúng lúc hoạt động đầu tiên kết thúc, nên không thể diễn ra sau hoạt động đó. Thực hiện hoạt động từ 1 đến 5 rồi đến hoạt động từ 9 đến 12 là được, nên đáp án là 2.

Đầu vào: start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
Đầu ra: 3
Giải thích: Khoảng từ 0 đến 100 chồng lấn lên tất cả các khoảng khác. Bỏ khoảng đó ra, 2 đến 4, 5 đến 7 và 8 đến 10 nối tiếp nhau: 3.

Câu hỏi mở rộng

Giờ đây, hai người làm việc song song, mỗi người thực hiện từng hoạt động một. Họ có thể cùng làm bao nhiêu hoạt động, và mỗi người nên đảm nhận hoạt động nào?

Lời giải

Thử mọi tập hợp con của các hoạt động sẽ tốn thời gian theo cấp số mũ. Thay vào đó, một quy tắc tham lam giúp giải quyết vấn đề: trong số các hoạt động vẫn còn phù hợp, luôn chọn hoạt động kết thúc sớm nhất. Sắp xếp theo thời gian kết thúc sẽ biến quy tắc đó thành một lượt duyệt duy nhất.

Chọn thời điểm kết thúc sớm nhất, lặp đi lặp lại

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Hoạt động kết thúc sớm nhất luôn là lựa chọn đầu tiên tốt ít nhất bằng mọi lựa chọn khác. Chọn hoạt động này không làm bạn phải chờ lâu hơn, nên mọi hoạt động có thể theo sau một lựa chọn đầu tiên khác cũng có thể theo sau nó, và việc đổi sang hoạt động này vẫn giữ nguyên số lượng. Sau lựa chọn đó, bài toán lặp lại với các hoạt động bắt đầu sau khi hoạt động này kết thúc.

Trong ví dụ đầu tiên, bạn chọn 10 đến 13, rồi 14 đến 19, rồi 21 đến 22, rồi 25 đến 30: tổng cộng bốn hoạt động.

Mỗi lần chọn, bạn quét tất cả n hoạt động, nên chi phí bằng n nhân với đáp án. Khi cả 5000 hoạt động đều có thể diễn ra nối tiếp nhau, việc này cần 25 triệu lượt kiểm tra.

Thuật toán

Đặt count = 0 và lastFinish = -1 bên dưới mọi điểm bắt đầu.
Duyệt qua tất cả hoạt động để tìm hoạt động có start[i] > lastFinish và kết thúc sớm nhất.
Nếu không có hoạt động nào, trả về count.
Nếu có, tăng count thêm 1, đặt lastFinish thành thời điểm kết thúc của hoạt động đó rồi duyệt lại.

def maxActivities(start, finish):
    n = len(start)
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    while True:
        # among the activities that start after last_finish, find the one that ends first
        pick = -1
        for i in range(n):
            if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
                pick = i
        if pick == -1:
            return count
        count += 1
        last_finish = finish[pick]

Sắp xếp theo thời gian kết thúc rồi chọn tham lam

Ý tưởng

Sắp xếp theo thời gian kết thúc, rồi bạn sẽ gặp các hoạt động theo thứ tự mà những lượt quét ở trên đã tìm kiếm chúng. Duyệt danh sách đã sắp xếp, giữ biến lastFinish, tức thời điểm kết thúc của hoạt động cuối cùng bạn chọn. Hoạt động có start[i] > lastFinish là hoạt động kết thúc sớm nhất vẫn phù hợp, vì vậy hãy chọn nó. Mọi hoạt động khác đều trùng với lựa chọn cuối của bạn, nên bỏ qua chúng cũng chẳng mất gì.

Sau khi sắp xếp, ví dụ đầu tiên có các khoảng thời gian 10 đến 13, 12 đến 16, 14 đến 19, 21 đến 22, 20 đến 24, 25 đến 30. Bạn chọn hoạt động thứ nhất, thứ ba, thứ tư và thứ sáu: 12 không sau 13, và 20 không sau 22.

Không cần quy tắc nào để xử lý các hoạt động có cùng thời gian kết thúc. Khi bạn chọn một hoạt động kết thúc tại t, mọi hoạt động khác cũng kết thúc tại t đều bắt đầu vào hoặc trước t và bị bỏ qua.

Thuật toán

Sắp xếp các hoạt động theo finish, di chuyển từng thời điểm bắt đầu cùng với thời điểm kết thúc tương ứng.
Đặt count = 0 và lastFinish = -1.
Với mỗi hoạt động theo thứ tự đó, nếu start[i] > lastFinish, tăng count thêm 1 và đặt lastFinish = finish[i].
Trả về count.

def maxActivities(start, finish):
    order = sorted(range(len(start)), key=lambda i: finish[i])  # earliest finish first
    count = 0
    last_finish = -1  # nothing taken yet; every start is at least 0
    for i in order:
        if start[i] > last_finish:
            count += 1
            last_finish = finish[i]
    return count

Lỗi thường gặp và trường hợp biên

Sắp xếp theo thời điểm bắt đầu. Trong ví dụ thứ ba, hoạt động từ 0 đến 100 bắt đầu trước và chặn ba hoạt động còn lại.
Chọn hoạt động ngắn nhất trước. Với các hoạt động từ 1 đến 5, từ 5 đến 6 và từ 6 đến 10, hoạt động ngắn nhất là từ 5 đến 6, nhưng hoạt động này xung đột với cả hai hoạt động còn lại; chọn hoạt động từ 1 đến 5 và từ 6 đến 10 thì được 2.
So sánh bằng ≥ thay vì >. Trong ví dụ thứ hai, cách này trả về 3 thay vì 2.
Chỉ sắp xếp finish. Mỗi thời điểm bắt đầu phải đi cùng thời điểm kết thúc tương ứng, nếu không, các thời điểm bắt đầu sẽ ghép với sai hoạt động.
Đặt lastFinish ban đầu là 0. Khi đó, một hoạt động duy nhất từ 0 đến 1 sẽ bị bỏ qua, vì 0 > 0 là false.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán chọn hoạt động là gì?

Việc sắp xếp theo thời gian kết thúc tốn O(n log n), còn lượt duyệt tham lam sau đó tốn O(n), nên phần sắp xếp chi phối độ phức tạp. Nếu các hoạt động đã được sắp xếp theo thời gian kết thúc, chỉ cần lượt duyệt là có thể giải quyết bài toán trong thời gian O(n) và dùng thêm không gian O(1).

Vấn đề N cuộc họp trong một phòng là gì?

Đây là cùng một bài toán nhưng kể qua các cuộc họp: một phòng, N cuộc họp, và một cuộc họp chỉ có thể bắt đầu sau khi cuộc họp trước kết thúc. Sắp xếp các cuộc họp theo thời gian kết thúc rồi chọn từng cuộc họp bắt đầu sau khi cuộc họp được chọn gần nhất kết thúc. Để liệt kê các cuộc họp, hãy ghi lại chỉ số của mỗi cuộc họp bạn chọn, và nếu thời gian kết thúc bằng nhau thì ưu tiên chỉ số nhỏ hơn.

Vấn đề chọn hoạt động có phải là quy hoạch động không?

Có thể dùng, nhưng không bắt buộc. Một bảng liệt kê các hoạt động được sắp xếp theo thời gian kết thúc, trong đó mỗi hoạt động ghi nhận số hoạt động nhiều nhất có thể kết thúc cùng nó, sẽ cho ra đáp án trong O(n²). Lựa chọn tham lam luôn an toàn, nên chỉ cần duyệt một lượt. Bảng là công cụ phù hợp khi các hoạt động có giá trị và bạn muốn tối đa hóa tổng giá trị của chúng.

def maxActivities(start, finish):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

start = [10, 12, 20, 14, 25, 21]
finish = [13, 16, 24, 19, 30, 22]

Đầu ra mong đợi