Non-overlapping Intervals

Q: Độ phức tạp thời gian của các khoảng không chồng lấn là gì?

Giải pháp tham lam sắp xếp theo thời điểm kết thúc trong O(n log n) rồi duyệt qua các khoảng một lần, nên độ phức tạp tổng thể là O(n log n) và cần O(n) bộ nhớ cho bản sao đã sắp xếp. Phiên bản quy hoạch động có độ phức tạp O(n²) , còn thử mọi tập hợp cần giữ lại có độ phức tạp O(2^n) .

Trung bìnhKhoảng Tham lam

+10

Khoảng thời gian i kéo dài từ starts[i] đến ends[i]. Hãy trả về số khoảng thời gian nhỏ nhất cần loại bỏ để không có hai khoảng nào còn lại chồng lấn. Hai khoảng chỉ tiếp xúc nhau, nghĩa là một khoảng kết thúc đúng tại điểm khoảng kia bắt đầu, thì không chồng lấn.

Hàm

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: phần đầu của mỗi khoảng thời gian
endsinteger-array: ở cuối mỗi khoảng, tại cùng chỉ số với điểm bắt đầu
Trả vềinteger: số khoảng thời gian ít nhất cần loại bỏ để các khoảng còn lại không chồng lấn

Ràng buộc

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Các khoảng không được sắp xếp. Hai khoảng có thể giống hệt nhau.

Ví dụ

Đầu vào: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Đầu ra: 2
Giải thích: Theo thứ tự bắt đầu, các khoảng là [1,4], [2,3], [3,6] và [5,7]. Giữ lại [2,3] và [3,6], vì chúng chỉ chạm nhau, đồng thời loại bỏ 2 khoảng còn lại. Không thể giữ lại 3 khoảng: [1,4] chồng lấn với [2,3], còn [3,6] chồng lấn với [5,7].

Đầu vào: starts = [0, 0, 0]ends = [5, 5, 5]
Đầu ra: 2
Giải thích: Cả ba khoảng đều là [0,5], nên bất kỳ hai khoảng nào cũng giao nhau. Giữ lại một khoảng và xóa 2.

Đầu vào: starts = [4, 1, 2]ends = [6, 2, 4]
Đầu ra: 0
Giải thích: [1,2], [2,4] và [4,6] nối tiếp nhau ở điểm cuối và điểm đầu, không bao giờ chồng lấn, nên bạn không loại bỏ gì cả và đáp án là 0.

Câu hỏi mở rộng

Giả sử mỗi khoảng có một giá trị và bạn muốn tìm tổng giá trị lớn nhất của các khoảng không chồng lấn. Việc chọn khoảng kết thúc sớm nhất có còn hiệu quả không?

Lời giải

Loại bỏ ít khoảng nhất tương đương với giữ lại nhiều khoảng không chồng lấn nhất: đáp án bằng n trừ đi số khoảng đó. Có thể tìm số lượng này bằng một quy tắc tham lam trong O(n log n): trong số các khoảng vẫn phù hợp, luôn giữ khoảng kết thúc sớm nhất.

Giữ lại hoặc xóa từng khoảng

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

Ý tưởng

Sắp xếp các khoảng theo điểm bắt đầu, rồi quyết định giữ lại hay loại bỏ từng khoảng. Bạn chỉ có thể giữ một khoảng nếu nó bắt đầu tại hoặc sau điểm kết thúc của khoảng được giữ gần nhất, nhờ vậy các khoảng được giữ tạo thành một chuỗi không chồng lấn. Thử cả hai lựa chọn ở mỗi khoảng và lấy số lượng lớn hơn; đáp án là n trừ đi số đó.

Mỗi khoảng có thể làm số nhánh tăng gấp đôi, vì vậy n khoảng có thể tạo ra đến 2^n đường đi. Chỉ cần 30 khoảng không chồng lấn cũng đã cần hơn một tỷ lời gọi, trong khi n có thể lên đến 5000.

Thuật toán

Sắp xếp các khoảng theo điểm bắt đầu, giữ mỗi điểm bắt đầu cùng với điểm kết thúc tương ứng.
Định nghĩa mostKept(i, last): số khoảng tối đa bạn có thể giữ từ vị trí i trở đi, khi last là khoảng được giữ gần nhất (-1 nếu chưa có khoảng nào).
Nếu đã vượt quá cuối danh sách, trả về 0. Nếu không, chọn mostKept(i+1, last), tức là loại bỏ khoảng i.
Nếu khoảng i bắt đầu tại hoặc sau điểm kết thúc của last, hãy thử thêm 1 + mostKept(i+1, i) và giữ giá trị lớn hơn.
Trả về n trừ mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Chuỗi dài nhất bằng quy hoạch động

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

Ý tưởng

Ta cứ hỏi đi hỏi lại cùng một câu: chuỗi dài nhất kết thúc bằng khoảng thời gian này dài bao lâu? Hãy trả lời câu hỏi đó một lần cho mỗi khoảng thời gian. Sắp xếp theo thời điểm bắt đầu và đặt chain[i] là số khoảng thời gian nhiều nhất bạn có thể giữ lại khi khoảng thời gian i đứng cuối.

Khoảng thời gian có thể đứng ngay trước i kết thúc vào hoặc trước starts[i], nên nó bắt đầu sớm hơn và đứng trước trong thứ tự đã sắp xếp. Vì vậy, chain[i] = 1 + chain[j] với j phù hợp nhất, hoặc bằng 1 nếu không có khoảng nào phù hợp. Trong ví dụ đầu tiên, các giá trị lần lượt là 1, 1, 2 và 2, nên bạn giữ lại 2 khoảng và loại bỏ 2 khoảng.

Vòng lặp kép thực hiện n(n-1)/2 lần kiểm tra: khoảng 12.5 triệu lần khi n = 5000.

Thuật toán

Sắp xếp các khoảng theo điểm bắt đầu, giữ mỗi điểm bắt đầu đi cùng điểm kết thúc của nó.
Đặt chain[i] = 1 cho mỗi khoảng.
Với mỗi i và mỗi j < i thỏa mãn ends[j] ≤ starts[i], đặt chain[i] thành chain[j]+1 nếu giá trị đó lớn hơn.
Lấy n trừ đi giá trị lớn nhất trong chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Tham lam: giữ khoảng thời gian kết thúc sớm nhất

Ý tưởng

Chọn khoảng có điểm kết thúc nhỏ nhất. Một lời giải tối ưu luôn giữ khoảng này: trong bất kỳ tập lớn nhất nào bạn có thể giữ lại, hãy thay khoảng xuất hiện sớm nhất bằng khoảng này. Khoảng này kết thúc không muộn hơn, nên vẫn kết thúc trước hoặc đúng lúc khoảng tiếp theo được giữ lại bắt đầu, và tập hợp vẫn giữ nguyên số lượng mà không có khoảng nào chồng lấn. Mọi khoảng bắt đầu trước điểm kết thúc của nó đều chồng lấn với nó và phải bị loại, còn lại cùng một bài toán với các khoảng bắt đầu tại hoặc sau điểm kết thúc đó.

Trong ví dụ đầu tiên, sau khi sắp xếp theo điểm kết thúc, bạn giữ [2,3], loại [1,4], giữ [3,6] và loại [5,7]. Thay vào đó, giữ khoảng ngắn nhất sẽ không hiệu quả với [1,5], [4,7], [6,10]: [4,7] chồng lấn với cả hai khoảng còn lại và khiến ta phải loại hai khoảng trong khi chỉ cần loại một.

Việc sắp xếp tốn O(n log n) và việc duyệt tốn O(n).

Thuật toán

Sắp xếp các khoảng theo điểm kết thúc, giữ mỗi điểm kết thúc cùng với điểm bắt đầu tương ứng.
Giữ khoảng đầu tiên: đặt lastEnd bằng điểm kết thúc của khoảng đó và đặt removed bằng 0.
Với mỗi khoảng tiếp theo, nếu điểm bắt đầu lớn hơn hoặc bằng lastEnd, giữ khoảng đó và đặt lastEnd bằng điểm kết thúc của nó.
Nếu không, cộng 1 vào removed.
Trả về removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

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

Coi các khoảng tiếp giáp là chồng lấn. Khi dùng start > lastEnd thay vì start ≥ lastEnd, chuỗi [1,2], [2,4], [4,6] cho kết quả 1 thay vì 0.
Sắp xếp theo điểm bắt đầu và giữ khoảng xuất hiện trước khi bị chồng lấn. Khoảng rộng [0,100] sẽ loại [1,2], [3,4] và [5,6]: cần loại bỏ ba khoảng thay vì một.
So sánh mỗi khoảng với khoảng liền kề trong danh sách đã sắp xếp thay vì khoảng cuối cùng được giữ lại. Trong ví dụ đầu tiên, cần kiểm tra [3,6] với điểm kết thúc của [2,3], chứ không phải của khoảng đã bị loại [1,4], nếu không kết quả sẽ là 3.
Sắp xếp starts và ends thành hai danh sách riêng. Mỗi điểm kết thúc phải luôn đi cùng điểm bắt đầu của nó.
Trả về số khoảng bạn giữ lại thay vì số khoảng bạn loại bỏ.

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

Độ phức tạp thời gian của các khoảng không chồng lấn là gì?

Giải pháp tham lam sắp xếp theo thời điểm kết thúc trong O(n log n) rồi duyệt qua các khoảng một lần, nên độ phức tạp tổng thể là O(n log n) và cần O(n) bộ nhớ cho bản sao đã sắp xếp. Phiên bản quy hoạch động có độ phức tạp O(n²), còn thử mọi tập hợp cần giữ lại có độ phức tạp O(2^n).

Bạn có thể sắp xếp theo thời gian bắt đầu thay vì vậy không?

Đúng, nhưng quy tắc xử lý phần chồng lấn khác. Duyệt các khoảng theo điểm bắt đầu. Khi khoảng tiếp theo chồng lấn với khoảng được giữ lại gần nhất, hãy đếm một lần xóa và giữ khoảng nào kết thúc trước. Cách này cho cùng kết quả trong cùng thời gian O(n log n).

Bài toán khoảng không giao nhau có giống bài toán chọn hoạt động không?

Đây là mặt còn lại của vấn đề. Bài toán chọn hoạt động yêu cầu tìm số khoảng thời gian không chồng lấn nhiều nhất; bài toán này yêu cầu tìm số khoảng thời gian cần loại bỏ ít nhất, bằng n trừ đi số đó. Cùng một quy tắc tham lam, giữ lại hoạt động kết thúc sớm nhất, giải quyết được cả hai bài toán.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

Non-overlapping Intervals

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Giữ lại hoặc xóa từng khoảng

Chuỗi dài nhất bằng quy hoạch động

Tham lam: giữ khoảng thời gian kết thúc sớm nhất

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

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

Bài tập tương tự