Chèn khoảng mới vào mảng khoảng đã sắp xếp trong JavaScript

Để mục đích câu hỏi này, chúng ta định nghĩa một khoảng (interval) là một mảng hai số nơi số đầu tiên luôn nhỏ hơn số thứ hai.

Ví dụ:

[4, 6], [2, 3], [6, 8], [2, 7], [1, 8] là tất cả các ví dụ của khoảng hợp lệ.

Giả sử, chúng ta có một mảng các khoảng được sắp xếp theo thời gian bắt đầu (phần tử đầu của mỗi khoảng).

Các khoảng trong mảng không chồng chéo, nghĩa là với bất kỳ hai khoảng liền kờ tùy ý:

[m, n], [x, y] m < n < x < y

Do đó, một ví dụ của mảng khoảng như vậy có thể là:

const arr = [[ 2, 4], [5, 7], [9, 10], [13, 17]];

Chúng ta cần viết một hàm JavaScript nhận vào một mảng khoảng như vậy làm đối số đầu tiên và một khoảng đơn lẻ làm đối số thứ hai.

Hàm sau đó nên chèn khoảng tại vị trí đúng trong mảng, duy trì tính chất không chồng chéo của mảng khoảng.

Nếu cần, chúng ta có thể gộp hai hoặc nhiều khoảng trong mảng để giữ các khoảng không chồng chéo.

Ví dụ, nếu cho mảng khoảng trên, khoảng cần chèn là [6, 13] Thì đầu ra nên trông như:

const output = [[2, 4], [5, 17]];

Ví dụ

Dưới đây là mã nguồn:

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));

Kết quả

Đầu ra trên console:

[[2, 4], [5, 17]]

Giải thích: Bài toán "Insert Interval" (LeetCode 57). 3 bước: 1) Thêm khoảng trước newInterval (không overlap). 2) Merge tất cả khoảng overlap với newInterval (cập nhật start=min, end=max). 3) Thêm các khoảng sau. O(n) time.