Chương trình tìm tín chỉ tối đa có thể đạt được bằng cách hoàn thành bài tập đúng hạn bằng Python

Cho hai danh sách deadlines và credits cùng kích thước, đại diện cho các bài tập. deadlines[i] là ngày hạn nộp, credits[i] là tín chỉ nhận được. Mỗi bài tập mất 1 ngày, phải hoàn thành vào hoặc trước ngày hạn. Không thể làm nhiều bài cùng lúc. Tìm tổng tín chỉ lớn nhất có thể đạt được.

Ví dụ: deadlines = [1, 2, 2, 2], credits = [4, 5, 6, 7] → kết quả 18 (làm bài 5 ngày 0, bài 6 ngày 1, bài 7 ngày 2).

Giải thuật

• Ghép cặp (deadline, credit) và sắp xếp giảm dần theo credit.
• Tạo mảng res kích thước max(deadlines)+1 đánh dấu ngày đã dùng.
• Duyệt từng cặp (i, j) (deadline, credit): từ ngày i giảm về 0, tìm ngày trống đầu tiên, đánh dấu và cộng tín chỉ.
• Trả về tổng tín chỉ.

Ví dụ minh họa

class Solution:
    def solve(self, deadlines, credits):
        a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
        if not a:
            return 0
        res = [0] * (max(deadlines) + 1)
        ans = 0
        for i, j in a:
            for k in range(i, -1, -1):
                if not res[k]:
                    res[k] = 1
                    ans += j
                    break
        return ans

ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

Đầu vào

[1, 2, 2, 2], [4, 5, 6, 7]

Đầu ra

18