630. Course Schedule III
Đề bài yêu cầu tính số khóa học tối đa thỏa mãn yêu cầu. mỗi khóa học chứa thông tin độ dài mỗi khóa, thời gian phải kết thúc.
Greedy solution:
Chắc chắn bạn phải học những khóa có thời gian kết thúc gần trước, nghĩa là hãy sort các khóa học theo thời gian kết thúc. Duyệt các khóa học nà, lưu lại tổng thời gian tham gia khóa học và duration của khóa học vào priority queue sort theo duration tăng dần.
Giả sử tổng thời gian khóa học là time, với mỗi khóa học i, nếu time + duration khóa học i <= thời gian kết thúc khóa học i thì ta sẽ thêm vào queue.
Khi không thể thêm được vào queue lúc này ta kiểm tra với khóa học có thời gian duration nhỏ nhất, nếu ít hơn ta sẽ thay thế khóa học này bằng khóa học tối ưu hơn để giảm tổng thời gian mà vẫn có số khóa học tương đương
Đề bài yêu cầu tính số khóa học tối đa thỏa mãn yêu cầu. mỗi khóa học chứa thông tin độ dài mỗi khóa, thời gian phải kết thúc.
Greedy solution:
Chắc chắn bạn phải học những khóa có thời gian kết thúc gần trước, nghĩa là hãy sort các khóa học theo thời gian kết thúc. Duyệt các khóa học nà, lưu lại tổng thời gian tham gia khóa học và duration của khóa học vào priority queue sort theo duration tăng dần.
Giả sử tổng thời gian khóa học là time, với mỗi khóa học i, nếu time + duration khóa học i <= thời gian kết thúc khóa học i thì ta sẽ thêm vào queue.
Khi không thể thêm được vào queue lúc này ta kiểm tra với khóa học có thời gian duration nhỏ nhất, nếu ít hơn ta sẽ thay thế khóa học này bằng khóa học tối ưu hơn để giảm tổng thời gian mà vẫn có số khóa học tương đương