Pattern · KhoảngTrung bình
Chèn Một KhoảngInsert Interval
Hiểu bài
Cho danh sách các khoảng (intervals) đã sắp xếp tăng dần theo start và không chồng nhau, cùng một khoảng mới newInterval.
Chèn newInterval vào, gộp nếu chồng, giữ kết quả vẫn sắp xếp và không chồng.
ts
intervals = [[1,3],[6,9]], newInterval = [2,5]
output = [[1,5],[6,9]] // [2,5] chồng [1,3] → gộp thành [1,5]Vì input đã sắp xếp, ta quét một lần theo 3 giai đoạn: các khoảng nằm hẳn trước newInterval, các khoảng chồng newInterval (gộp lại), rồi phần còn lại nằm sau.
Cách cơ bản
O(n log n) timets
function insertNaive(intervals: number[][], newInterval: number[]): number[][] {
const all = [...intervals, newInterval]
all.sort((a, b) => a[0] - b[0]) // input vốn đã sắp xếp → sort lại là thừa
// ... rồi chạy đúng thuật toán Merge Intervals trên 'all'
return mergeIntervals(all)
}Vì sao cách này chậm:
Cách này nhét newInterval vào rồi sắp xếp lại và gộp như bài Merge Intervals.
Đúng nhưng phí bước sắp xếp vì input đã sắp xếp sẵn — quét tuyến tính chỉ tốn O(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.