Insert Interval

Q: Độ phức tạp thời gian của Insert Interval là gì?

Giải pháp duyệt một lượt có thời gian chạy O(n) , vì mỗi khoảng được sao chép hoặc gộp vào đúng một lần, đồng thời dùng O(n) bộ nhớ cho kết quả có tối đa n+1 khoảng. Thêm khoảng rồi sắp xếp lại mất O(n log n) .

Q: Insert Interval khác với Merge Intervals như thế nào?

Merge Intervals bắt đầu với một danh sách chưa được sắp xếp, trong đó bất kỳ khoảng nào cũng có thể chồng lấn với khoảng khác, nên trước tiên thuật toán sẽ sắp xếp danh sách. Ở đây, danh sách đã được sắp xếp và các khoảng cũ không bao giờ chạm nhau, nên chỉ khoảng mới có thể kích hoạt việc gộp, và các khoảng được gộp với nó tạo thành một đoạn liên tiếp. Chỉ cần duyệt một lượt.

Q: Làm thế nào để kiểm tra xem hai khoảng có chồng lấn không?

[a, b] và [c, d] có chung một điểm khi và chỉ khi a ≤ d và c ≤ b . Theo yêu cầu của bài toán này, điều đó tính cả các khoảng chạm nhau như [2, 4] và [4, 8] là chồng lấp. Để giữ các khoảng chạm nhau tách biệt, hãy dùng a < d và c < b .

Trung bìnhKhoảng

+10

Bạn nhận được các khoảng đã sắp xếp theo điểm bắt đầu dưới dạng hai mảng: khoảng thứ i là [starts[i], ends[i]], và không có hai khoảng nào chồng lấp hoặc tiếp giáp nhau. Chèn khoảng mới [newStart, newEnd], gộp khoảng này với mọi khoảng chồng lấp hoặc tiếp giáp với nó, rồi trả về tất cả các khoảng dưới dạng cặp [start, end], được sắp xếp theo điểm bắt đầu.

Các khoảng tiếp giáp nhau khi điểm kết thúc của khoảng này trùng với điểm bắt đầu của khoảng kia, như [2, 4] và [4, 8], và các khoảng tiếp giáp sẽ được gộp. [1, 2] và [3, 4] không có điểm chung, nên chúng vẫn tách rời.

Hàm

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: điểm bắt đầu của mỗi khoảng, theo thứ tự tăng dần
endsinteger-array: điểm kết thúc của mỗi khoảng, tương ứng với điểm bắt đầu
newStartinteger: điểm bắt đầu của khoảng cần chèn
newEndinteger: điểm kết thúc của khoảng cần chèn
Trả vềinteger-2d-array: các khoảng sau khi chèn dưới dạng cặp [start, end], được sắp xếp theo start

Ràng buộc

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: các khoảng được sắp xếp theo điểm bắt đầu, và không có hai khoảng nào chồng lấn hoặc tiếp giáp nhau.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Ví dụ

Đầu vào: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Đầu ra: [[1, 3], [5, 12], [15, 18]]
Giải thích: [6, 11] chồng lấn với [5, 7] và [10, 12], nên cả ba hợp thành [5, 12]. [1, 3] kết thúc trước 6 và [15, 18] bắt đầu sau 12, nên cả hai vẫn giữ nguyên.

Đầu vào: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Đầu ra: [[2, 9]]
Giải thích: [4, 8] tiếp giáp với [2, 4] tại 4 và [8, 9] tại 8, vì vậy cả ba gộp lại thành [2, 9].

Đầu vào: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Đầu ra: [[1, 2], [5, 6], [9, 10]]
Giải thích: [5, 6] nằm trong khoảng giữa 2 và 9, không chạm vào phần tử nào bên cạnh, nên nó được chèn vào giữa chúng và không có gì được gộp lại.

Câu hỏi mở rộng

Nếu bạn chèn nhiều khoảng thời gian liên tiếp, bạn sẽ lưu chúng như thế nào để mỗi lần chèn tốn O(log n) cộng thêm một bước cho mỗi khoảng thời gian cũ mà nó gộp vào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Các khoảng cũ đã được sắp xếp và không giao nhau, vì vậy chỉ khoảng mới có thể gây ra việc gộp. Điều đó chia danh sách thành ba nhóm: các khoảng kết thúc trước khi khoảng mới bắt đầu, các khoảng giao nhau hoặc tiếp giáp với khoảng mới, và các khoảng bắt đầu sau khi khoảng mới kết thúc. Sao chép nhóm đầu tiên, gộp nhóm ở giữa thành một khoảng, rồi sao chép nhóm cuối cùng. Chỉ cần duyệt một lượt, không cần sắp xếp.

Thêm nó vào rồi gộp mọi thứ lại

Ý tưởng

Tái sử dụng cách gộp các khoảng: thêm khoảng mới, sắp xếp tất cả n+1 khoảng theo điểm bắt đầu, rồi duyệt qua chúng và giữ khoảng đã gộp gần nhất. Sau khi sắp xếp, một khoảng chỉ có thể chồng lấp với nhóm ngay trước nó, vì vậy khi điểm bắt đầu tiếp theo nằm trước hoặc trùng với điểm kết thúc đang giữ, hãy kéo dài điểm kết thúc; nếu không, một khoảng trống xuất hiện và một khoảng mới bắt đầu.

Việc sắp xếp tốn O(n log n) để sửa danh sách chỉ bị sai thứ tự ở một vị trí, đồng thời bỏ qua việc các khoảng cũ không bao giờ gộp với nhau.

Thuật toán

Ghép mỗi điểm bắt đầu với điểm kết thúc tương ứng, rồi thêm [newStart, newEnd] vào danh sách.
Sắp xếp các khoảng theo điểm bắt đầu.
Duyệt lần lượt, giữ khoảng cuối cùng đã gộp.
Nếu điểm bắt đầu tiếp theo nhỏ hơn hoặc bằng điểm kết thúc đang giữ, cập nhật điểm kết thúc đang giữ thành giá trị lớn hơn trong hai điểm kết thúc.
Nếu không, thêm khoảng tiếp theo làm khoảng mới đã gộp. Trả về danh sách các khoảng đã gộp.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Một lượt gồm ba phần

Ý tưởng

Danh sách đã được sắp xếp và các khoảng không chồng lấn, nên những khoảng giao với khoảng mới tạo thành một dãy liên tục. Mọi khoảng trước dãy này đều có ends[i] < newStart: chúng kết thúc trước khi khoảng mới bắt đầu. Điều kiện kiểm tra phải chặt vì khoảng kết thúc đúng tại newStart sẽ tiếp giáp với khoảng mới và cần được gộp.

Trong dãy này, một khoảng có starts[i] ≤ mergedEnd chồng lấn hoặc tiếp giáp với khoảng bạn đang tạo, vì vậy nó mở rộng khoảng đó đến điểm bắt đầu nhỏ hơn và điểm kết thúc lớn hơn. Khoảng đầu tiên bắt đầu sau mergedEnd đánh dấu kết thúc dãy, vì mọi khoảng sau đó đều bắt đầu xa hơn về bên phải. Nếu dãy rỗng, khoảng mới được thêm riêng. Trong ví dụ đầu tiên, [1, 3] được sao chép, [5, 7] và [10, 12] mở rộng [6, 11] thành [5, 12], còn [15, 18] được sao chép. Ta chỉ xét mỗi khoảng một lần: thời gian O(n) và không cần thêm bộ nhớ ngoài kết quả.

Thuật toán

Sao chép các khoảng vào kết quả khi ends[i] < newStart.
Đặt mergedStart = newStart và mergedEnd = newEnd.
Khi starts[i] ≤ mergedEnd, đặt mergedStart thành giá trị bắt đầu nhỏ hơn và mergedEnd thành giá trị kết thúc lớn hơn, rồi chuyển sang phần tiếp theo.
Thêm [mergedStart, mergedEnd].
Sao chép các khoảng còn lại và trả về kết quả.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Lỗi thường gặp và trường hợp biên

Dùng sai các phép so sánh để kiểm tra các khoảng có chạm nhau không. Nếu dùng ends[i] ≤ newStart trong vòng lặp đầu tiên hoặc starts[i] < mergedEnd trong vòng lặp thứ hai, [2, 4] và [4, 8] sẽ không được gộp. Phép so sánh thứ nhất phải nghiêm ngặt, phép thứ hai thì không.
So sánh với mergedEnd + 1. Cách này gộp [1, 2] và [3, 4], dù chúng không có điểm chung.
Giữ newStart làm điểm bắt đầu của khoảng đã gộp. [6, 11] bắt đầu bên trong [5, 7], nên kết quả phải bắt đầu từ 5.
Chỉ thêm khoảng mới khi nó chồng lấp với khoảng khác. Khi khoảng mới nằm ở chỗ trống hoặc vượt quá một trong hai đầu, như [5, 6], vòng lặp ở giữa sẽ không chạy, nhưng bạn vẫn phải thêm khoảng đó.
Đọc starts[i] trước khi kiểm tra i < n. Một khoảng mới vượt quá khoảng cuối cùng sẽ khiến chỉ số chạy ra ngoài phạm vi.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Insert Interval là gì?

Giải pháp duyệt một lượt có thời gian chạy O(n), vì mỗi khoảng được sao chép hoặc gộp vào đúng một lần, đồng thời dùng O(n) bộ nhớ cho kết quả có tối đa n+1 khoảng. Thêm khoảng rồi sắp xếp lại mất O(n log n).

Insert Interval khác với Merge Intervals như thế nào?

Merge Intervals bắt đầu với một danh sách chưa được sắp xếp, trong đó bất kỳ khoảng nào cũng có thể chồng lấn với khoảng khác, nên trước tiên thuật toán sẽ sắp xếp danh sách. Ở đây, danh sách đã được sắp xếp và các khoảng cũ không bao giờ chạm nhau, nên chỉ khoảng mới có thể kích hoạt việc gộp, và các khoảng được gộp với nó tạo thành một đoạn liên tiếp. Chỉ cần duyệt một lượt.

Làm thế nào để kiểm tra xem hai khoảng có chồng lấn không?

[a, b] và [c, d] có chung một điểm khi và chỉ khi a ≤ d và c ≤ b. Theo yêu cầu của bài toán này, điều đó tính cả các khoảng chạm nhau như [2, 4] và [4, 8] là chồng lấp. Để giữ các khoảng chạm nhau tách biệt, hãy dùng a < d và c < b.

def insertInterval(starts, ends, newStart, newEnd):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Đầu ra mong đợi

[[1, 3], [5, 12], [15, 18]]