Meeting Rooms

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

Sắp xếp các cuộc họp theo thời gian bắt đầu tốn O(n log n) , còn việc duyệt qua và so sánh các phần tử liền kề tốn O(n) , nên tổng thời gian là O(n log n) . So sánh mọi cặp tốn O(n²) .

Q: Các cuộc họp có thời gian trùng nhau có được tính là chồng lấn không?

Trong bài toán này thì không: một cuộc họp có thể bắt đầu đúng thời điểm cuộc họp trước kết thúc, vì vậy điều kiện kiểm tra là start < previous end theo nghĩa nghiêm ngặt. Nếu không cho phép các cuộc họp liền kề nhau, điều kiện sẽ là start ≤ previous end .

Q: Làm thế nào để tìm số phòng họp tối thiểu?

Sắp xếp thời gian bắt đầu và thời gian kết thúc thành hai danh sách riêng, rồi duyệt cả hai: mỗi thời gian bắt đầu cần một phòng, còn mỗi thời gian kết thúc trước hoặc đúng lúc thời gian bắt đầu tiếp theo sẽ giải phóng một phòng. Số phòng được sử dụng cùng lúc nhiều nhất chính là đáp án. Bài toán này hỏi liệu một phòng có đủ hay không.

DễKhoảng Sắp xếp

+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ột người muốn tham dự tất cả các cuộc họp, vì vậy không có hai cuộc họp nào được trùng thời gian. Một cuộc họp có thể bắt đầu đúng lúc cuộc họp khác kết thúc. Trả về true nếu người đó có thể tham dự mọi cuộc họp, nếu không thì trả về false.

Hàm

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

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, ở cùng chỉ số với thời gian bắt đầu
Trả vềboolean: true nếu không có hai cuộc họp nào bị trùng lịch, false nếu không

Ràng buộc

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

Ví dụ

Đầu vào: starts = [9, 13, 10]ends = [10, 15, 12]
Đầu ra: true
Giải thích: Theo thứ tự thời gian, các cuộc họp diễn ra từ 9 đến 10, từ 10 đến 12 và từ 13 đến 15. Cuộc họp thứ hai bắt đầu ngay khi cuộc họp thứ nhất kết thúc, điều này được phép, nên đáp án là true.

Đầu vào: starts = [1, 4, 7]ends = [5, 6, 8]
Đầu ra: false
Giải thích: Cuộc họp từ 1 đến 5 vẫn đang diễn ra lúc 4, khi cuộc họp từ 4 đến 6 bắt đầu, nên đáp án là false.

Câu hỏi mở rộng

Nếu các cuộc họp được đặt lần lượt, bạn sẽ kiểm tra từng cuộc họp mới với lịch trình trong O(log n) như thế nào mà không cần sắp xếp lại mọi thứ?

Lời giải

Kiểm tra mọi cặp cuộc họp sẽ tìm ra mọi trường hợp trùng lịch trong O(n²). Thay vào đó, hãy sắp xếp theo thời gian bắt đầu: khi đó, một cuộc họp chỉ có thể trùng lịch với cuộc họp liền kề trong thứ tự đã sắp xếp, vì vậy chỉ cần so sánh một lần cho mỗi cuộc họp.

So sánh từng cặp

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

Ý tưởng

Hai cuộc họp xung đột khi mỗi cuộc bắt đầu trước khi cuộc kia kết thúc: với khoảng từ 1 đến 5 và từ 4 đến 6, 1 nhỏ hơn 6 và 4 nhỏ hơn 5. Dùng toán tử < nghiêm ngặt ở cả hai phía giúp các cuộc họp từ 9 đến 10 và từ 10 đến 12 tiếp giáp nhau mà không xung đột. Kiểm tra mọi cặp và trả về false ngay khi gặp xung đột đầu tiên.

Với n = 5000, có khoảng 12,5 triệu cặp, và nếu lịch không có xung đột, bạn sẽ phải kiểm tra tất cả.

Thuật toán

Với mỗi chỉ số i và mỗi chỉ số j đứng sau nó:
Nếu starts[i] < ends[j] và starts[j] < ends[i], hai cuộc họp bị chồng lấn: trả về false.
Nếu không có cặp nào bị chồng lấn, trả về true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Sắp xếp theo điểm bắt đầu và kiểm tra các phần tử liền kề

Ý tưởng

Sắp xếp các cuộc họp theo thời gian bắt đầu, giữ mỗi thời gian bắt đầu đi cùng thời gian kết thúc tương ứng. Nếu đến giờ chưa phát hiện cuộc họp nào bị trùng, thì các cuộc họp đã xét tạo thành một chuỗi, mỗi cuộc họp bắt đầu vào lúc hoặc sau khi cuộc họp trước đó kết thúc. Vì vậy, cuộc họp ngay trước cuộc họp mới kết thúc muộn nhất, và cuộc họp mới bắt đầu vào lúc hoặc sau thời điểm đó sẽ không trùng với cuộc họp nào. Cuộc họp bắt đầu trước thời điểm đó sẽ bị trùng.

Các cuộc họp có cùng thời gian bắt đầu luôn bị trùng, vì mỗi cuộc họp kéo dài ít nhất một đơn vị thời gian, và phép kiểm tra trên cũng phát hiện được trường hợp này. Sắp xếp tốn O(n log n), duyệt tốn O(n), và bản sao ghép cặp của các cuộc họp cần O(n) bộ nhớ.

Thuật toán

Ghép mỗi thời điểm bắt đầu với thời điểm kết thúc tương ứng.
Sắp xếp các cặp theo thời điểm bắt đầu.
Với mỗi cuộc họp sau cuộc họp đầu tiên, so sánh thời điểm bắt đầu với thời điểm kết thúc của cuộc họp trước đó.
Nếu thời điểm bắt đầu nhỏ hơn, trả về false.
Sau vòng lặp, trả về true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

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

Sắp xếp starts nhưng giữ nguyên thứ tự đầu vào của ends. Mỗi thời điểm kết thúc phải đi cùng thời điểm bắt đầu tương ứng, nếu không, bạn sẽ so sánh thời điểm bắt đầu của cuộc họp này với thời điểm kết thúc của cuộc họp khác.
Dùng ≤ thay vì <. Các cuộc họp từ 9 đến 10 và từ 10 đến 12 chỉ vừa chạm nhau, nên kết quả là true.
So sánh các cuộc họp liền kề theo thứ tự đầu vào. Đầu vào chưa được sắp xếp: các cuộc họp từ 1 đến 5, từ 7 đến 8, từ 4 đến 6 không có xung đột giữa các cuộc họp liền kề, nhưng cuộc họp đầu tiên và cuối cùng lại trùng nhau.
Viết phép kiểm tra một cặp bằng một điều kiện, chẳng hạn như starts[j] < ends[i]. Với hai cuộc họp từ 5 đến 6 và từ 0 đến 1 theo thứ tự đó, 0 < 6 báo có xung đột dù thực tế không có.

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

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

Sắp xếp các cuộc họp theo thời gian bắt đầu tốn O(n log n), còn việc duyệt qua và so sánh các phần tử liền kề tốn O(n), nên tổng thời gian là O(n log n). So sánh mọi cặp tốn O(n²).

Các cuộc họp có thời gian trùng nhau có được tính là chồng lấn không?

Trong bài toán này thì không: một cuộc họp có thể bắt đầu đúng thời điểm cuộc họp trước kết thúc, vì vậy điều kiện kiểm tra là start < previous end theo nghĩa nghiêm ngặt. Nếu không cho phép các cuộc họp liền kề nhau, điều kiện sẽ là start ≤ previous end.

Làm thế nào để tìm số phòng họp tối thiểu?

Sắp xếp thời gian bắt đầu và thời gian kết thúc thành hai danh sách riêng, rồi duyệt cả hai: mỗi thời gian bắt đầu cần một phòng, còn mỗi thời gian kết thúc trước hoặc đúng lúc thời gian bắt đầu tiếp theo sẽ giải phóng một phòng. Số phòng được sử dụng cùng lúc nhiều nhất chính là đáp án. Bài toán này hỏi liệu một phòng có đủ hay không.

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

Kiểm thử #1

Kiểm thử #2

Đối số

starts = [9, 13, 10]
ends = [10, 15, 12]

Đầu ra mong đợi

true