Dự Hết Các Cuộc Họp?Meeting Rooms
Hiểu bài
Cho danh sách các cuộc họp intervals, mỗi cuộc là [start, end]. Hỏi: một người có thể dự tất cả các cuộc họp không (không cuộc nào trùng giờ)? Trả về true/false.
Ví dụ:
intervals = [[0, 30], [5, 10], [15, 20]]
output = false // [5,10] đè lên [0,30]
intervals = [[7, 10], [2, 4]]
output = trueCuộc họp chạm mép ([1,5] và [5,8]) coi như KHÔNG trùng — cuộc trước vừa xong thì cuộc sau bắt đầu.
Xem cách cơ bản (chậm hơn)
O(n²) time, O(1) spacefunction canAttendMeetings(intervals: number[][]): boolean {
for (let i = 0; i < intervals.length; i++) {
for (let j = i + 1; j < intervals.length; j++) {
const [s1, e1] = intervals[i]
const [s2, e2] = intervals[j]
if (s1 < e2 && s2 < e1) return false // có giao nhau
}
}
return true
}So từng cặp cuộc họp xem có đè nhau không.
Đúng nhưng tốn — với n lớn thì n² phép so sánh là thừa, vì sau khi sắp xếp ta chỉ cần so cuộc liền kề.
Lời giải tối ưu
O(n log n) time, O(1) spacefunction canAttendMeetings(intervals: number[][]): boolean {
intervals.sort((a, b) => a[0] - b[0]) // theo giờ bắt đầu tăng dần
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false // cuộc này bắt đầu trước khi cuộc trước kết thúc
}
}
return true
}Sắp theo giờ bắt đầu, khi đó nếu có trùng giờ thì chắc chắn xảy ra giữa hai cuộc liền kề — không cần so mọi cặp.
Chỉ cần kiểm tra: giờ bắt đầu của cuộc sau có sớm hơn giờ kết thúc của cuộc ngay trước không.
Chạy thử từng bước
- 1
Hình dung intervals = [[1,5], [6,8], [7,9]].
- Sắp theo start (đã đúng thứ tự).
- Bắt đầu so từ i=1.
sorted:[[1,5],[6,8],[7,9]] - 2
i=1: cuộc [6,8], start=6 < end cuộc trước [1,5] = 5? Không (6 ≥ 5) → chưa trùng, đi tiếp.
i:1start:6prevEnd:5conflict:false - 3
i=2: cuộc [7,9], start=7 < end cuộc trước [6,8] = 8? Có → trùng giờ, trả về false ngay.
i:2start:7prevEnd:8conflict:trueresult:false
Trường hợp biên phải nhớ
Chạm mép
[1,5],[5,8]: dùng<(không phải<=) khi so start với prevEnd, nên 5 < 5 sai → coi là dự được, đúng yêu cầu.Danh sách rỗng hoặc đúng 1 cuộc → luôn true (không có gì để đè).
Input chưa sắp theo thời gian — bắt buộc sort trước, nếu không thuật toán so cuộc liền kề sẽ sai.
Nhiều cuộc cùng giờ bắt đầu ([2,4],[2,5]) → 2 < 4 → false.