Job Sequencing Problem

Q: Độ phức tạp thời gian của bài toán sắp xếp công việc là bao nhiêu?

Với tập hợp rời nhau, độ phức tạp thời gian là O(n log n) , chủ yếu do thao tác sắp xếp, và độ phức tạp không gian là O(n) . Quét ngược từ mỗi thời hạn để tìm một vị trí trống sẽ tốn O(n²) khi phần lớn thời hạn có giá trị lớn.

Trung bìnhTham lam Sắp xếp

+10

Bạn có n công việc được biểu diễn bằng hai mảng: công việc i mang lại profit[i] nếu hoàn thành trước hoặc đúng thời điểm deadline[i]. Mỗi công việc mất một đơn vị thời gian, bạn chạy từng công việc một, bắt đầu từ thời điểm 0 và có thể bỏ qua bất kỳ công việc nào. Công việc có hạn chót là 2 có thể chạy từ 0 đến 1 hoặc từ 1 đến 2.

Trả về tổng lợi nhuận lớn nhất bạn có thể kiếm được.

Hàm

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: thời hạn hoàn thành của từng công việc, từ 1 đến n
profitinteger-array: thu nhập của từng công việc; profit[i] tương ứng với deadline[i]
Trả vềinteger: tổng lợi nhuận lớn nhất từ các công việc có thể hoàn thành đúng hạn

Ràng buộc

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, trong đó n là số lượng công việc
1 ≤ profit[i] ≤ 10⁵
Các mảng không được sắp xếp. Nhiều công việc có thể có cùng hạn chót hoặc lợi nhuận.

Ví dụ

Đầu vào: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
Đầu ra: 120
Giải thích: Chỉ có một trong hai công việc có hạn chót 1 phù hợp, nên hãy chạy công việc có giá trị 50. Công việc có giá trị 30 hoàn thành đúng hạn chót 2, còn công việc có giá trị 40 hoàn thành đúng hạn chót 3: 50 + 30 + 40 = 120.

Đầu vào: deadline = [1, 1, 1]profit = [5, 9, 7]
Đầu ra: 9
Giải thích: Cả ba công việc đều phải hoàn thành trước thời điểm 1, nhưng chỉ có một công việc kịp hoàn thành trước lúc đó. Công việc tốt nhất trong số đó mang lại 9.

Câu hỏi mở rộng

Nếu công việc i mất duration[i] đơn vị thời gian thay vì một đơn vị thì sao? Chọn công việc có lợi nhuận cao nhất trước có còn cho tổng lợi nhuận tốt nhất không?

Lời giải

Bạn chọn những công việc cần giữ lại và thời điểm chạy chúng. Một quy tắc tham lam giải quyết cả hai việc: xét các công việc theo thứ tự lợi nhuận giảm dần, rồi xếp mỗi công việc vào ô trống muộn nhất trước hoặc đúng hạn chót của nó, bỏ qua công việc nếu không còn ô trống nào. Cấu trúc dữ liệu tập hợp rời rạc tìm ô đó mà không phải đi qua những ô đã được xếp lịch.

Tham lam theo lợi nhuận, quét tìm vị trí trống

Ý tưởng

Chia thời gian thành các khung: khung t chạy từ t-1 đến t, một công việc có hạn chót d có thể dùng các khung từ 1 đến d, và không hạn chót nào vượt quá n. Chọn công việc có lợi nhuận cao nhất trước là an toàn: nếu mọi khung nó có thể dùng đều đã kín, đổi nó lấy công việc ở một trong các khung đó sẽ thu được ít nhất bằng mức lợi nhuận. Xếp công việc vào khung muộn nhất là an toàn vì chỉ các khung sớm mới dùng được cho những công việc có hạn chót sớm.

Chi phí nằm ở việc quét. Khi mọi hạn chót đều là n, công việc thứ k phải đi qua k-1 khung đã kín: khoảng n²/2, tương đương 12.5 triệu bước khi n = 5000.

Thuật toán

Sắp xếp các công việc theo lợi nhuận, từ lớn nhất đến nhỏ nhất, giữ mỗi hạn chót đi kèm với lợi nhuận tương ứng.
Tạo một mảng taken gồm n + 1 cờ, tất cả đều là false.
Với mỗi công việc, giảm dần t từ hạn chót của công việc xuống 1 và dừng ở vị trí đầu tiên chưa được lấy.
Nếu tìm thấy một vị trí như vậy, đánh dấu vị trí đó đã được lấy và cộng lợi nhuận của công việc vào total.
Trả về total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

Thuật toán tham lam theo lợi nhuận với cấu trúc tập hợp rời rạc cho các vị trí trống

Ý tưởng

Quá trình quét đi qua cùng một số khung giờ đã đặt nhiều lần. Cấu trúc tập hợp rời rạc trên các khung giờ từ 0 đến n giúp bỏ qua chúng: parent[t] = t khi khung giờ t còn trống, còn khi đặt khung giờ đó, ta gán parent[t] = t-1, nhờ vậy lần theo các con trỏ từ hạn chót sẽ đến khung giờ trống muộn nhất. Đến khung giờ 0 nghĩa là không còn khung giờ nào. Phép nén đường đi trỏ mỗi khung giờ mà bạn đi qua đến khung giờ cách trước nó hai bước, nhờ vậy những lần đi sau ngắn hơn.

Trong ví dụ thứ ba, các công việc trị giá 60 và 50 được xếp vào khung giờ 2 và 1. Công việc trị giá 20, có hạn chót là 2, lần theo đường đi từ 2 đến 1 rồi đến 0 và bị bỏ qua.

Sắp xếp tốn O(n log n), còn với phép nén đường đi, mỗi lần tra cứu tốn O(log n) theo mức khấu hao, nên tổng thời gian vẫn là O(n log n).

Thuật toán

Sắp xếp các công việc theo lợi nhuận, từ lớn nhất đến nhỏ nhất, đồng thời giữ hạn chót đi kèm với lợi nhuận tương ứng.
Đặt parent[t] = t cho mọi vị trí t từ 0 đến n.
Với mỗi công việc, bắt đầu tại slot = deadline rồi lần theo parent cho đến khi parent[slot] == slot, đồng thời rút ngắn đường đi.
Nếu slot > 0, cộng lợi nhuận của công việc và đặt parent[slot] = slot-1; nếu không, bỏ qua công việc.
Trả về tổng.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

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

Đặt công việc vào vị trí trống sớm nhất. Trong ví dụ thứ ba, công việc trị giá 60 sẽ chiếm vị trí 1, còn công việc trị giá 50 sẽ bị bỏ lỡ: bạn kiếm được 80 thay vì 110.
Chọn công việc theo thứ tự thời hạn. Với thời hạn [1, 1] và lợi nhuận [1, 100], công việc có lợi nhuận thấp chiếm vị trí duy nhất, nên bạn kiếm được 1 thay vì 100.
Tạo mảng vị trí có kích thước n thay vì n + 1. Khi đó, thời hạn bằng n sẽ khiến chương trình đọc vượt quá giới hạn cuối mảng.
Sắp xếp riêng lợi nhuận. Mỗi thời hạn phải đi cùng với lợi nhuận tương ứng.
Viết bước tìm kiếm bằng đệ quy. Một chuỗi liên kết qua hàng nghìn vị trí đã được đặt trước có thể làm tràn ngăn xếp; hãy dùng vòng lặp.

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

Độ phức tạp thời gian của bài toán sắp xếp công việc là bao nhiêu?

Với tập hợp rời nhau, độ phức tạp thời gian là O(n log n), chủ yếu do thao tác sắp xếp, và độ phức tạp không gian là O(n). Quét ngược từ mỗi thời hạn để tìm một vị trí trống sẽ tốn O(n²) khi phần lớn thời hạn có giá trị lớn.

Tại sao cách tiếp cận tham lam lại hiệu quả với bài toán sắp xếp công việc?

Một lịch tối ưu bất kỳ đều chứa công việc có lợi nhuận cao nhất. Nếu lịch chưa có công việc đó và còn chỗ trống trước hạn chót, thêm công việc này sẽ giúp tăng lợi nhuận; nếu mọi chỗ như vậy đều đã kín, đổi một công việc khác thành công việc này sẽ mang lại lợi nhuận ít nhất bằng hiện tại. Lập luận này tiếp tục áp dụng cho những công việc còn lại.

Bài toán sắp xếp công việc có thể được giải bằng heap không?

Đúng vậy. Hãy sắp xếp các công việc theo hạn chót rồi đẩy lợi nhuận của từng công việc vào một đống tối thiểu (min-heap). Mỗi khi đống chứa nhiều công việc hơn số lượng hạn chót hiện tại cho phép, hãy lấy ra lợi nhuận nhỏ nhất. Cuối cùng, đống chứa tập hợp công việc tốt nhất và tổng lợi nhuận của chúng là đáp án, với độ phức tạp O(n log n).

def jobSequencing(deadline, profit):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

Đầu ra mong đợi