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
}Giải thuật tối ưu sử dụng 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
1function eraseOverlapIntervals(intervals: number[][]): number {2intervals.sort((a, b) => a[1] - b[1]) // theo điểm KẾT THÚC tăng dần3let prevEnd = -Infinity4let removed = 05for (const [start, end] of intervals) {6if (start >= prevEnd) {7prevEnd = end // không chồng → giữ khoảng này8} else {9removed++ // chồng lấn → bỏ (khoảng kết thúc muộn hơn)10}11}12return removed13}
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.