Meeting Rooms II

+10

Bạn nhận được danh sách các cuộc họp dưới dạng hai mảng: cuộc họp i diễn ra từ starts[i] đến ends[i]. Mỗi phòng chỉ chứa một cuộc họp tại một thời điểm, và một cuộc họp có thể bắt đầu trong phòng đúng lúc cuộc họp khác tại đó kết thúc.

Viết một hàm tên là minMeetingRooms trả về số phòng ít nhất có thể chứa tất cả các cuộc họp.

Hàm

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

startsinteger-array: thời gian bắt đầu của mỗi cuộc họp
endsinteger-array: thời gian kết thúc của mỗi cuộc họp, tại cùng chỉ số với thời gian bắt đầu
Trả vềinteger: số phòng ít nhất có thể chứa tất cả các cuộc họp

Ràng buộc

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Các cuộc họp chưa được sắp xếp. Hai cuộc họp có thể giống hệt nhau.

Ví dụ

Đầu vào: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Đầu ra: 3
Giải thích: Vào thời điểm 4, các cuộc họp từ 1 đến 5, từ 2 đến 6 và từ 4 đến 8 đều đang diễn ra, nên bạn cần ít nhất 3 phòng. Ba phòng là đủ: cuộc họp từ 7 đến 9 sử dụng phòng được giải phóng lúc 5.

Đầu vào: starts = [0, 2, 3]ends = [10, 3, 5]
Đầu ra: 2
Giải thích: Cuộc họp từ 0 đến 10 dùng một phòng trong suốt thời gian đó. Các cuộc họp từ 2 đến 3 và từ 3 đến 5 dùng chung phòng thứ hai, nên cần 2 phòng là đủ.

Câu hỏi mở rộng

Bạn cũng có thể cho biết mỗi cuộc họp diễn ra ở phòng nào, mà không dùng nhiều phòng hơn số phòng trong lời giải không?

Lời giải

Bạn cần số phòng bằng số cuộc họp đang diễn ra cùng lúc nhiều nhất. Đếm số cuộc họp đang diễn ra tại mỗi thời điểm bắt đầu sẽ tốn O(n²). Sắp xếp giúp bạn duyệt qua cả ngày một lượt, dùng heap tối thiểu chứa thời điểm các phòng trống hoặc hai danh sách đã sắp xếp gồm thời điểm bắt đầu và kết thúc, với độ phức tạp O(n log n).

Đếm số cuộc họp đang diễn ra tại mỗi thời điểm bắt đầu

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

Ý tưởng

Số cuộc họp đang diễn ra chỉ tăng khi một cuộc họp bắt đầu, nên thời điểm đông nhất là lúc bắt đầu của một cuộc họp nào đó. Với mỗi cuộc họp i, hãy đếm các cuộc họp j thỏa mãn starts[j] ≤ starts[i] < ends[j]. Không tính cuộc họp kết thúc đúng lúc starts[i]: phòng họp của cuộc họp đó lại trống. Trong ví dụ đầu tiên, tại thời điểm 4 có ba cuộc họp đang diễn ra và tại thời điểm 7 có hai cuộc họp, nên đáp án là 3.

Mỗi trong số n cuộc họp đều duyệt qua toàn bộ n cuộc họp: n = 5000 nghĩa là có 25 triệu lần kiểm tra.

Thuật toán

Với mỗi cuộc họp i, đặt running thành 0.
Với mỗi cuộc họp j, tăng running thêm 1 khi starts[j] ≤ starts[i] < ends[j].
Giữ lại giá trị lớn nhất của running mà bạn đã thấy.
Trả về giá trị lớn nhất đó.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

Đống tối thiểu lưu các thời điểm phòng trống

Ý tưởng

Xét các cuộc họp theo thứ tự thời gian bắt đầu và chỉ kiểm tra phòng trống sớm nhất. Nếu phòng đó vẫn đang có người khi cuộc họp bắt đầu thì tất cả các phòng đều đang bận, vì vậy bạn mở thêm một phòng. Nếu phòng đó đang trống, phòng trống nào cũng như nhau: các cuộc họp tiếp theo bắt đầu không sớm hơn, nên một phòng đang trống sẽ vẫn trống cho tất cả các cuộc họp đó.

Min-heap lưu một thời điểm kết thúc cho mỗi phòng và trả về thời điểm nhỏ nhất. Trong ví dụ đầu tiên, sau khi sắp xếp theo thời gian bắt đầu, heap phát triển thành [5, 6, 8]. Cuộc họp từ 7 đến 9 thấy thời điểm 5 không muộn hơn 7 và thay thế nó, để lại [6, 8, 9]: ba phòng. Việc sắp xếp tốn O(n log n), còn mỗi cuộc họp cần một thao tác trên heap với độ phức tạp O(log n).

Thuật toán

Sắp xếp các cuộc họp theo thời điểm bắt đầu, giữ mỗi thời điểm bắt đầu đi cùng thời điểm kết thúc tương ứng.
Với mỗi cuộc họp, nếu heap không rỗng và thời điểm kết thúc nhỏ nhất nhỏ hơn hoặc bằng thời điểm bắt đầu của cuộc họp, hãy thay thời điểm kết thúc đó bằng thời điểm kết thúc của cuộc họp.
Nếu không, hãy thêm thời điểm kết thúc của cuộc họp vào heap: một phòng mới được mở.
Trả về kích thước của heap, mỗi phần tử tương ứng với một phòng.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

Sắp xếp thời điểm bắt đầu và kết thúc riêng biệt

Ý tưởng

Đáp án là một số đếm, vì vậy ở mỗi thời điểm bắt đầu, bạn chỉ cần biết liệu đã có cuộc họp nào kết thúc hay chưa, chứ không cần biết đó là cuộc họp nào. Sắp xếp thời điểm bắt đầu và thời điểm kết thúc thành hai danh sách riêng, rồi duyệt các thời điểm bắt đầu bằng một con trỏ ended trỏ đến danh sách thời điểm kết thúc. Nếu một cuộc họp bắt đầu vào hoặc sau endTimes[ended], cuộc họp đó dùng phòng vừa được giải phóng; nếu không, bạn cần mở thêm một phòng.

Số đếm này chính xác. Khi rooms tăng, thời điểm kết thúc tiếp theo vẫn còn ở tương lai, nên tại thời điểm đó, cả rooms cuộc họp đều đang diễn ra. Một cuộc họp chỉ không cần mở thêm phòng khi có một cuộc họp thực sự đã kết thúc vào hoặc trước thời điểm đó và giải phóng phòng. Trong ví dụ đầu tiên, các thời điểm bắt đầu 1, 2 và 4 đều trước thời điểm kết thúc 5, nên rooms tăng lên 3; thời điểm bắt đầu 7 dùng lại phòng được giải phóng ở thời điểm 5. Hai lần sắp xếp tốn O(n log n), còn lượt duyệt tốn O(n).

Thuật toán

Sắp xếp một bản sao của danh sách thời điểm bắt đầu và một bản sao của danh sách thời điểm kết thúc.
Đặt rooms và ended thành 0.
Với mỗi thời điểm bắt đầu theo thứ tự, nếu thời điểm đó bằng hoặc sau endTimes[ended], hãy tăng ended thêm 1: cuộc họp sử dụng một phòng vừa được giải phóng.
Nếu không, hãy tăng rooms thêm 1.
Trả về rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

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

Kiểm tra start > end thay vì start ≥ end. Khi một cuộc họp vừa kết thúc, cuộc họp tiếp theo không thể dùng ngay phòng đó, nên các cuộc họp từ 10 đến 12, 12 đến 14 và 14 đến 16 cần 2 phòng thay vì 1.
Kiểm tra phòng bạn mở sau cùng thay vì phòng được giải phóng sớm nhất. Với các cuộc họp từ 1 đến 3, 2 đến 10 và 4 đến 6, bạn mở phòng thứ ba lúc 4 dù phòng đầu tiên đã trống từ lúc 3.
Trả lời bằng số cuộc họp chồng lấn với một cuộc họp cộng thêm 1. Cuộc họp từ 0 đến 10 chồng lấn với các cuộc họp từ 2 đến 3 và từ 3 đến 5, nhưng hai cuộc họp đó không bao giờ chồng lấn với nhau, nên 2 phòng là đủ.

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

Độ phức tạp thời gian của MinMeetingRooms là bao nhiêu?

Cả lời giải dùng heap và lời giải dùng hai danh sách đều chạy trong thời gian O(n log n) và cần thêm O(n) bộ nhớ. Phần sắp xếp chiếm phần lớn chi phí; bước duyệt sau đó tốn O(n log n) với heap và O(n) với hai danh sách.

Liệu có thể giải bài toán MinMeetingRooms bằng thuật toán đường quét không?

Đúng vậy. Biến mỗi cuộc họp thành một sự kiện +1 tại thời điểm bắt đầu và một sự kiện -1 tại thời điểm kết thúc, sắp xếp các sự kiện rồi theo dõi tổng lũy kế lớn nhất. Nếu các sự kiện có cùng thời điểm, hãy xử lý sự kiện kết thúc trước sự kiện bắt đầu để các cuộc họp nối tiếp nhau có thể dùng chung một phòng.

Đáp án có bằng số cuộc họp chồng lấn nhiều nhất tại cùng một thời điểm không?

Đúng. Các cuộc họp diễn ra cùng lúc cần phòng riêng, vì vậy bạn cần ít nhất từng ấy phòng. Nếu xếp cho mỗi cuộc họp, theo thứ tự bắt đầu, một phòng bất kỳ đang trống thì bạn không bao giờ cần nhiều hơn. Vì vậy, số cuộc họp diễn ra đồng thời nhiều nhất chính là đáp án.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

Meeting Rooms II

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Đếm số cuộc họp đang diễn ra tại mỗi thời điểm bắt đầu

Đống tối thiểu lưu các thời điểm phòng trống

Sắp xếp thời điểm bắt đầu và kết thúc riêng biệ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ự