Pattern · KhoảngTrung bình
Gộp Các KhoảngMerge Intervals
Hiểu bài
Cho danh sách các khoảng (intervals) intervals[i] = [start, end].
Gộp mọi khoảng chồng nhau và trả về danh sách các khoảng không còn chồng.
ts
intervals = [[1,3],[2,6],[8,10],[15,18]]
output = [[1,6],[8,10],[15,18]]
// [1,3] và [2,6] chồng nhau (2 <= 3) → gộp thành [1,6]Ý chính: sắp xếp theo điểm bắt đầu trước.
Khi đã sắp xếp, một khoảng chỉ có thể chồng với khoảng vừa thêm vào kết quả — nên chỉ cần so với phần tử cuối, không phải mọi cặp.
Cách cơ bản
O(n²) time trở lênts
function mergeNaive(intervals: number[][]): number[][] {
const used = new Array(intervals.length).fill(false)
const result: number[][] = []
for (let i = 0; i < intervals.length; i++) {
if (used[i]) continue
let [start, end] = intervals[i]
let changed = true
while (changed) { // quét lại toàn bộ tìm khoảng chồng để gộp
changed = false
for (let j = 0; j < intervals.length; j++) {
if (used[j] || j === i) continue
const [s, e] = intervals[j]
if (s <= end && start <= e) {
start = Math.min(start, s); end = Math.max(end, e)
used[j] = true; changed = true
}
}
}
result.push([start, end])
}
return result
}Vì sao cách này chậm:
Không sắp xếp nên mỗi khoảng phải so với mọi khoảng khác, lặp lại nhiều lần.
Sắp xếp trước đưa bài về một lần quét, tổng O(n log n).
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.