Lesson 20 — Interval Problems (Greedy trên khoảng)
Ba module tương tác cho 3 khuôn mẫu interval: Activity Selection (sort theo end), Merge Intervals (sort theo start), Meeting Rooms (sweep line — max concurrent / min phòng). Mấu chốt mọi bài: chọn đúng tiêu chí sort.
1. Activity Selection — sort theo end, chọn greedy
Sort các hoạt động theo thời điểm kết thúc, rồi chọn cái nào tương thích
(bắt đầu ≥ end của cái vừa chọn). Biên nửa mở [s, e): chạm đầu-cuối không tính chồng.
chưa xét
đang xét
đã chọn
bỏ (chồng)
Bấm "Sort theo end" để bắt đầu.
2. Merge Intervals — sort theo start, gộp overlap
Sort theo thời điểm bắt đầu, quét từ trái: nếu khoảng mới chồng/chạm khoảng
đang gộp thì nới biên phải bằng max; rời hẳn thì chốt và mở khoảng mới. Biên đóng
[s, e]: chạm = gộp.
input
đang xét
khoảng đã gộp (kết quả)
Bấm "Sort theo start" để bắt đầu.
3. Meeting Rooms — sweep line (max concurrent = min phòng)
Mỗi cuộc họp [s, e) → 2 event: +1 tại start, −1 tại end.
Sort event theo thời điểm (tie: −1 trước +1 cho biên nửa mở), quét cộng dồn.
Giá trị cao nhất = số phòng tối thiểu.
cuộc họp
+1 (start)
−1 (end)
Bấm "Quét 1 event" để bắt đầu sweep line.