Bỏ Ít Khoảng Nhất Cho Hết Chồng LấnNon-overlapping Intervals
Hiểu bài
Cho danh sách intervals, mỗi khoảng là [start, end]. Trả về số khoảng ít nhất phải bỏ đi để các khoảng còn lại không chồng lấn nhau.
Ví dụ:
intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
// bỏ [1, 3] là đủ → còn [1,2],[2,3],[3,4] không chồng nhau
output = 1Hai khoảng chạm nhau ở mép ([1,2] và [2,3]) KHÔNG tính là chồng lấn.
Lời giải tối ưu
O(n log n) time, O(1) spacefunction eraseOverlapIntervals(intervals: number[][]): number {
intervals.sort((a, b) => a[1] - b[1]) // theo điểm KẾT THÚC tăng dần
let prevEnd = -Infinity
let removed = 0
for (const [start, end] of intervals) {
if (start >= prevEnd) {
prevEnd = end // không chồng → giữ khoảng này
} else {
removed++ // chồng lấn → bỏ (khoảng kết thúc muộn hơn)
}
}
return removed
}Mẹo tham lam: sắp theo điểm KẾT THÚC, luôn giữ khoảng kết thúc sớm nhất vì nó "chừa chỗ" nhiều nhất cho các khoảng sau.
Khi gặp khoảng bắt đầu trước prevEnd (chồng lấn), bỏ chính nó đi — vì nó kết thúc muộn hơn (do đã sắp theo end) nên giữ lại chỉ thiệt.
Chạy thử từng bước
- 1
Sắp theo điểm kết thúc tăng dần: [[1,2], [1,3], [2,3], [3,4]].
Khởi tạo prevEnd = −∞, removed = 0.
sorted:[[1,2],[1,3],[2,3],[3,4]]prevEnd:"-∞"removed:0 - 2
[1,2]: start=1 ≥ prevEnd(−∞) → giữ, cập nhật prevEnd = 2.
interval:[1,2]prevEnd:2removed:0 - 3
[1,3]: start=1 ≥ prevEnd(2)? Không → chồng lấn, bỏ nó. removed = 1. prevEnd giữ nguyên 2.
interval:[1,3]prevEnd:2removed:1 - 4
[2,3]: 2 ≥ 2 → giữ, prevEnd = 3. [3,4]: 3 ≥ 3 → giữ, prevEnd = 4.
Kết thúc: removed = 1.
lastKept:[3,4]prevEnd:4removed:1
Trường hợp biên phải nhớ
Khoảng chạm mép
[1,2]và[2,3]: dùngstart >= prevEnd(dấu ≥) để coi là KHÔNG chồng — nếu dùng>sẽ bỏ nhầm.Mọi khoảng giống hệt nhau ([[1,2],[1,2],[1,2]]) → giữ 1, bỏ n−1.
Danh sách rỗng hoặc 1 khoảng → trả 0.
Sắp theo START thay vì END là cái bẫy kinh điển: với [[1,100],[2,3],[3,4]] sắp theo start sẽ giữ [1,100] và bỏ 2 khoảng nhỏ — sai.
Phải sắp theo end.