cpp-343Bước 1Cơ bản
Chọn nhiều khoảng thời gian không giao nhau nhất
Một phòng họp nhỏ có nhiều yêu cầu đặt chỗ, mỗi yêu cầu là một khoảng thời gian từ lúc bắt
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Thuật toán Tham lam (Greedy Algorithm) trong C++
Đưa ra lựa chọn tốt nhất ở từng bước để đạt được lời giải tối ưu toàn cục. Học cách nhận diện bài toán thỏa mãn tính chất tham lam và chứng minh lời giải.
9
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
3
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
5
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
1
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Tư duy Tham lam cơ bản
Sắp xếp theo tiêu chí phù hợp và chọn lựa chọn có lợi nhất ở bước hiện tại.
Bước 2
Lập lịch & Xếp đoạn
Bài toán chọn số lượng công việc không giao nhau nhiều nhất bằng cách sắp xếp theo thời gian kết thúc.
Bước 3
Kết hợp Priority Queue
Duy trì phần tử ưu tiên để cập nhật trạng thái tham lam liên tục.
Lỗi thường gặp & Cách phòng tránh
•
Áp dụng tham lam cho các bài toán cần quy hoạch động (không thỏa mãn thuộc tính lựa chọn tham lam).
•
Sắp xếp sai tiêu chí (ví dụ sắp xếp theo thời gian bắt đầu thay vì thời gian kết thúc).
Danh sách bài tập thực hành (9 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Cơ bản 3 bài
cpp-344Bước 2Cơ bản
Đổi tiền bằng ít đồng xu nhất
Máy đổi tiền chỉ có bốn loại xu mệnh giá 25, 10, 5 và 1. Với mỗi số tiền cần trả,
cpp-345Bước 3Cơ bản
Số phòng họp tối thiểu cần dùng
Một công ty nhận được nhiều yêu cầu đặt phòng họp, mỗi yêu cầu là một khoảng thời gian từ
Trung bình 5 bài
cpp-153Bước 1Trung bình
Nối Dây Kim Loại Chi Phí Nhỏ Nhất (Mã Hóa Huffman / Priority Queue)
Có N sợi dây kim loại, sợi thứ i có độ dài Li. Bạn cần nối tất cả N sợi dây này lại thành một sợi dây duy nhất.
cpp-150Bước 2Trung bình
Xếp Lịch Phòng Họp Không Trùng Lặp Tối Đa (Interval Scheduling)
Có N cuộc họp đăng ký sử dụng một phòng hội nghị duy nhất. Cuộc họp thứ i bắt đầu tại thời điểm Si và kết thúc tại thời điểm Ei (Si < Ei).
cpp-152Bước 3Trung bình
Bài Toán Ba-Lô Phân Số (Fractional Knapsack)
Có N món đồ kim loại quý dạng hạt/bột. Món đồ thứ i có giá trị Vi và trọng lượng Wi. Bạn có một chiếc ba-lô với sức chứa tối đa là C.
cpp-151Bước 4Trung bình
Hành Trình Qua Các Trạm Xăng Vòng Tròn (Gas Station)
Trên một cung đường tròn có N trạm xăng được đánh số từ 1 đến N theo chiều kim đồng hồ.
cpp-088Bước 5Trung bình
Xử lý khoảng thời gian: Gộp khoảng và Lập lịch tác vụ tối đa
Cho N khoảng thời gian [Li, Ri]. Hãy gộp tất cả các khoảng thời gian bị chồng lấn (overlapping) hoặc tiếp xúc nhau thành các khoảng rời rạc cực đại.
Nâng cao 1 bài
cpp-094Bước 1Nâng cao
Lập lịch khóa học: Tham lam kết hợp Hàng đợi ưu tiên Max-Heap
1. Sắp xếp các khóa học theo hạn chót (Deadline) tăng dần.
