Khoảng — Intervals
Nhóm bài "khoảng" (intervals) làm việc với danh sách các cặp [bắt đầu, kết thúc] — lịch họp, đoạn thời gian, dải số. Bước nền tảng gần như luôn là sắp xếp theo điểm bắt đầu.
Sau khi sắp xếp, một khoảng chỉ có thể chồng lên khoảng liền trước trong kết quả, nên ta chỉ cần quét một lần để gộp hoặc chèn. Điểm dễ sai là định nghĩa "chồng nhau" tại biên (dùng < hay <=) và việc cập nhật điểm kết thúc bằng giá trị lớn nhất của hai khoảng.
Như xếp lịch họp một phòng — mỗi cuộc họp là một khoảng [bắt đầu, kết thúc].
- Sắp xếp theo giờ bắt đầu rồi quét từ trái sang: khoảng mới chồng khoảng trước thì gộp lại, không chồng thì mở khoảng mới.
- Sắp xếp trước là chìa khoá để chỉ cần so với khoảng liền kề.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Khoảng
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| danh sách [start, end] | Sắp xếp theo start trước khi quét |
| gộp khoảng chồng nhau | end mới = max(end hiện tại, end đang xét) |
| lịch / phòng / tài nguyên | Đếm số khoảng chồng nhau cùng lúc |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Gộp các khoảng chồng nhau (merge intervals)
Chèn một khoảng mới vào danh sách đã sắp xếp
Đếm số phòng / tài nguyên cần để không trùng lịch
Tìm phần giao / phần còn trống giữa các khoảng
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Chỉ có 1-2 interval đơn lẻ: xử lý case riêng nhanh hơn dùng thuật toán tổng quát
Interval thay đổi liên tục (insert / delete động): cân nhắc Interval Tree / Segment Tree
Bài tối ưu chọn interval theo trọng số (weighted scheduling): đây là bài DP / Greedy khác
Hình minh hoạ
Sơ đồ thể hiện cách giải của chủ đề này.
Sắp theo điểm bắt đầu rồi gộp khi khoảng sau chồng lên khoảng trước. [1,3] và [2,6] chồng nhau → [1,6]; [8,10] rời nên giữ nguyên.
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function intervalPattern(intervals: number[][]): number[][] {
// 1. Sắp xếp theo điểm bắt đầu
intervals.sort((a, b) => a[0] - b[0])
const result: number[][] = []
for (const [start, end] of intervals) {
const last = result[result.length - 1]
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end) // chồng nhau → gộp
} else {
result.push([start, end]) // không chồng → khoảng mới
}
}
return result
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Hầu hết bài bắt đầu bằng sort theo start: O(n log n)
Hai khoảng a, b chồng nhau khi a.start <= b.end và b.start <= a.end
Khi gộp: end mới = max(end hiện tại, end khoảng đang xét)
Lỗi thường gặp
Quên sort trước khi quét → bỏ sót khoảng chồng ở xa
So sai điều kiện chồng nhau (nhầm < với <=) ở các khoảng chạm biên
Cập nhật end bằng end khoảng mới thay vì max của hai end
Độ phức tạp
Sắp xếp O(n log n) rồi quét 1 lần O(n)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay