บทความนี้สาธิตการแทรก interval ใหม่เข้าไปในอาร์เรย์ของ intervals ที่จัดเรียงแล้วและไม่ทับซ้อนกัน โดย merge ช่วงที่ทับซ้อนกัน
ตัวอย่าง
arr = [[2,4], [5,7], [9,10], [13,17]] interval = [6,13] output: [[2,4], [5,17]]
ตัวอย่างโค้ด
const arr = [[2, 4], [5, 7], [9, 10], [13, 17]];
const interval = [6, 13];
const insertWithin = (arr = [], interval = []) => {
const res = [];
let ind = 0;
while (arr[ind] && arr[ind][1] < interval[0]) {
res.push(arr[ind]);
++ind;
}
let start = interval[0];
let end = interval[1];
while (arr[ind] && arr[ind][0] <= interval[1]) {
start = Math.min(start, arr[ind][0]);
end = Math.max(end, arr[ind][1]);
++ind;
}
res.push([start, end]);
while (arr[ind]) {
res.push(arr[ind]);
++ind
}
return res;
};
console.log(insertWithin(arr, interval));
ผลลัพธ์
[[2, 4], [5, 17]]
คำอธิบาย
3 ขั้นตอน: 1) เพิ่ม intervals ที่จบก่อน interval ใหม่ 2) merge intervals ที่ทับซ้อนกับ interval ใหม่ (start = min, end = max) 3) เพิ่ม intervals ที่เหลือ
Time: O(n), Space: O(n)
