Merge Intervals

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

Giải pháp sắp xếp và quét chạy trong thời gian O(n log n) với n khoảng: bước sắp xếp tốn O(n log n), còn bước quét tốn O(n). Giải pháp dùng thêm O(n) không gian cho các cặp đã sắp xếp và kết quả.

Q: Tại sao sắp xếp các khoảng theo điểm bắt đầu thay vì điểm kết thúc?

Khi sắp xếp theo điểm bắt đầu, một khoảng chỉ có thể chồng lấp với nhóm bạn đang tạo, vì vậy chỉ cần so sánh với điểm kết thúc của nhóm đó là đủ để quyết định. Khi sắp xếp theo điểm kết thúc, một khoảng ở phía sau có thể bắt đầu trước những nhóm bạn đã kết thúc: [5, 6] đứng trước [1, 10] , và nếu duyệt xuôi, bạn sẽ sai lầm khi giữ 5 làm điểm bắt đầu.

Q: Bạn có thể gộp các khoảng mà không cần thêm không gian không?

Có, nếu bạn có thể thay đổi đầu vào. Sắp xếp các khoảng ngay trong mảng, rồi ghi đè từng khoảng đã gộp lên phần đầu của chính mảng đó và giữ chỉ số của khoảng cuối cùng đã ghi. Thời gian vẫn là O(n log n), còn bộ nhớ bổ sung duy nhất là phần mà thao tác sắp xếp của ngôn ngữ bạn sử dụng.

Trung bìnhKhoảng Sắp xếp

+10

Bạn nhận được một tập hợp các khoảng, mỗi khoảng là một dãy số nguyên từ điểm bắt đầu đến điểm kết thúc. Gộp từng nhóm khoảng chồng lấp thành một khoảng bao phủ toàn bộ nhóm, rồi trả về các khoảng đã gộp, được sắp xếp theo điểm bắt đầu. Các khoảng chỉ chạm nhau, như [1, 4] và [4, 5], cũng được tính là chồng lấp.

Các khoảng được truyền vào dưới dạng hai mảng có cùng độ dài: khoảng i là [starts[i], ends[i]]. Bạn trả về một mảng 2D, tức danh sách các cặp [start, end].

Hàm

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: phần đầu của mỗi khoảng
endsinteger-array: ở cuối mỗi khoảng, tại cùng chỉ số với điểm bắt đầu của khoảng đó
Trả vềinteger-2d-array: các khoảng đã gộp dưới dạng các cặp [start, end], sắp xếp theo start

Ràng buộc

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Các khoảng thời gian có thể đến theo bất kỳ thứ tự nào.
Các khoảng chỉ tiếp xúc tại một đầu mút cũng được tính là chồng lấp.

Ví dụ

Đầu vào: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Đầu ra: [[1, 7], [12, 14]]
Giải thích: Theo thứ tự bắt đầu, [1, 4] chồng lấn với [3, 6], khoảng này chồng lấn với [5, 7], nên cả ba hợp thành [1, 7]. [12, 14] bắt đầu sau 7 và vẫn đứng riêng.

Câu hỏi mở rộng

Các khoảng đã được gộp và sắp xếp theo điểm bắt đầu. Bạn cần thêm một khoảng mới. Bạn có thể trả về danh sách đã gộp trong thời gian O(n) mà không sắp xếp lại không?

Lời giải

Gộp từng cặp theo thứ tự bất kỳ cần lặp lại nhiều lượt, vì mỗi lần gộp đều mở rộng một khoảng và có thể chạm đến những khoảng bạn đã kiểm tra. Thay vào đó, hãy sắp xếp theo điểm bắt đầu. Khi đó, một khoảng chỉ có thể chồng lấn với nhóm bạn đang tạo và bạn có thể hoàn tất công việc chỉ trong một lượt.

Gộp các cặp chồng lấn cho đến khi không còn thay đổi

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Các khoảng [a, b] và [c, d] chồng lấn khi c ≤ b và a ≤ d, còn [min(a, c), max(b, d)] bao phủ cả hai khoảng. Mỗi lần gộp sẽ loại bỏ một khoảng, nên quá trình sẽ dừng lại. Khi duyệt hết một lượt mà không tìm thấy chỗ chồng lấn nào, sẽ không còn hai khoảng nào cùng chứa một điểm. Một lượt là chưa đủ: khoảng sau khi gộp sẽ rộng hơn và có thể chạm đến một khoảng mà phần nhỏ hơn của nó đã được so sánh ở đầu lượt.

Mỗi lượt so sánh khoảng n²/2 cặp và bạn có thể cần đến n lượt: O(n³). Chỉ một lượt qua 10^4 khoảng cũng cần đến 5 × 10^7 lần so sánh.

Thuật toán

Sao chép starts và ends, rồi dùng biến đếm n để theo dõi số khoảng còn hiệu lực.
So sánh từng khoảng i với mọi khoảng j đứng sau nó. Nếu chúng chồng lấn, mở rộng i để bao phủ j, chuyển khoảng còn hiệu lực cuối cùng vào vị trí j và giảm n đi một.
Sau khi gộp, kiểm tra lại vị trí j, vì lúc này có một khoảng khác nằm ở đó.
Lặp lại các lượt cho đến khi có một lượt không gộp khoảng nào.
Ghép mỗi điểm bắt đầu còn hiệu lực với điểm kết thúc tương ứng, sắp xếp các cặp theo điểm bắt đầu rồi trả về chúng.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Sắp xếp theo điểm bắt đầu rồi quét một lượt

Ý tưởng

Sau khi sắp xếp theo điểm bắt đầu, khoảng tiếp theo bắt đầu không sớm hơn bất kỳ khoảng nào trong nhóm cuối, nhóm này kết thúc tại e. Nếu điểm bắt đầu của khoảng đó không lớn hơn e, nó chồng lấp hoặc tiếp giáp với nhóm nên được gộp vào nhóm, và e trở thành giá trị lớn hơn trong hai điểm kết thúc. Nếu điểm bắt đầu của nó nằm sau e, thì không khoảng nào về sau có thể kéo dài ngược vào nhóm, vì các khoảng sau bắt đầu xa hơn về bên phải. Nhóm đã hoàn tất, và khoảng đó mở ra một nhóm mới.

Việc sắp xếp tốn O(n log n), còn lượt quét đi qua mỗi khoảng đúng một lần. Các nhóm được đóng từ trái sang phải, nên kết quả được sắp xếp theo điểm bắt đầu.

Thuật toán

Ghép mỗi điểm bắt đầu với điểm kết thúc tương ứng: khoảng i là [starts[i], ends[i]].
Sắp xếp các cặp theo điểm bắt đầu.
Duyệt qua các cặp đã sắp xếp. Nếu kết quả đang rỗng, hoặc cặp bắt đầu sau điểm kết thúc của khoảng đã gộp cuối cùng, hãy thêm cặp đó làm một khoảng mới.
Nếu không, hãy đặt điểm kết thúc của khoảng đã gộp cuối cùng thành giá trị lớn hơn giữa điểm kết thúc của khoảng đó và điểm kết thúc của cặp.
Trả về danh sách đã gộp.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

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

So sánh với < thay vì ≤. Các khoảng chạm nhau như [1, 4] và [4, 5] phải được gộp lại.
Đặt điểm kết thúc thành điểm kết thúc của khoảng mới thay vì lấy giá trị lớn hơn trong hai điểm kết thúc. [1, 10] theo sau là [2, 3] phải giữ nguyên thành [1, 10].
Sắp xếp riêng starts rồi đọc ends ở các vị trí mới, khiến một điểm bắt đầu ghép với điểm kết thúc của khoảng khác. Hãy ghép chúng trước hoặc sắp xếp các chỉ số.
So sánh với khoảng đầu vào trước đó thay vì khoảng đã gộp gần nhất. Trong [1, 10], [2, 3], [4, 5], khoảng thứ ba nằm trong [1, 10] dù nó không chạm [2, 3].
Trong C, không đặt *returnSize thành số khoảng đã gộp và kích thước của mỗi cột thành 2.

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

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

Giải pháp sắp xếp và quét chạy trong thời gian O(n log n) với n khoảng: bước sắp xếp tốn O(n log n), còn bước quét tốn O(n). Giải pháp dùng thêm O(n) không gian cho các cặp đã sắp xếp và kết quả.

Tại sao sắp xếp các khoảng theo điểm bắt đầu thay vì điểm kết thúc?

Khi sắp xếp theo điểm bắt đầu, một khoảng chỉ có thể chồng lấp với nhóm bạn đang tạo, vì vậy chỉ cần so sánh với điểm kết thúc của nhóm đó là đủ để quyết định. Khi sắp xếp theo điểm kết thúc, một khoảng ở phía sau có thể bắt đầu trước những nhóm bạn đã kết thúc: [5, 6] đứng trước [1, 10], và nếu duyệt xuôi, bạn sẽ sai lầm khi giữ 5 làm điểm bắt đầu.

Bạn có thể gộp các khoảng mà không cần thêm không gian không?

Có, nếu bạn có thể thay đổi đầu vào. Sắp xếp các khoảng ngay trong mảng, rồi ghi đè từng khoảng đã gộp lên phần đầu của chính mảng đó và giữ chỉ số của khoảng cuối cùng đã ghi. Thời gian vẫn là O(n log n), còn bộ nhớ bổ sung duy nhất là phần mà thao tác sắp xếp của ngôn ngữ bạn sử dụng.

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

Kiểm thử #1

Kiểm thử #2

Đối số

starts = [5, 1, 12, 3]
ends = [7, 4, 14, 6]

Đầu ra mong đợi

[[1, 7], [12, 14]]