2402. Meeting Rooms III
Tags:
Hard
Skills:
Heap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Cho n phòng họp và danh sách các cuộc họp với thời gian bắt đầu/ kết thúc. Mỗi cuộc họp phải được xếp vào một phòng theo các quy tắc
Mục tiêu: Tìm phòng được sử dụng nhiều nhất. Nếu có nhiều phòng cùng số lần, chọn phòng có số nhỏ nhất
Phân tích
Approach
idle : Chứa các phòng đang rảnh (min-heap theo số phòng)busy : Chứa các phòng đang bận, mỗi phần tử là (thời điểm phòng rảnh, số phòng) count để đếm số lần mỗi phòng được sử dụngQuy trình
busy sang heap idle idle không rỗng), lấy phòng có số nhỏ nhất để đặt cuộc họpbusy , dời cuộc họp đến thời điểm phòng đó rảnh, và đặt vào phòng đóSolution
1type Room = {
2 endTime: number;
3 roomId: number;
4}
5
6function mostBooked(n: number, meetings: number[][]): number {
7 meetings.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
8 const available_rooms = new PriorityQueue<number>((a, b) => a - b);
9
10 for (let i = 0; i < n; i++) available_rooms.enqueue(i);
11
12 const busy_rooms = new PriorityQueue<Room>((a, b) => a.endTime - b.endTime || a.roomId - b.roomId);
13
14 const booking_count = new Array(n).fill(0);
15
16 for (const [start, end] of meetings) {
17 while (!busy_rooms.isEmpty() && busy_rooms.front().endTime <= start) {
18 const { roomId } = busy_rooms.dequeue()!;
19 available_rooms.enqueue(roomId);
20 }
21
22
23 if (!available_rooms.isEmpty()) {
24 const roomId = available_rooms.dequeue()!;
25 booking_count[roomId]++;
26 busy_rooms.enqueue({
27 endTime: end,
28 roomId
29 })
30 } else {
31 const earliest = busy_rooms.dequeue()!;
32 booking_count[earliest.roomId]++;
33 busy_rooms.enqueue({
34 endTime: earliest.endTime + (end - start),
35 roomId: earliest.roomId
36 })
37 }
38 }
39
40 let max_index = 0;
41 for (let i = 0; i < n; i++) {
42 if (booking_count[i] > booking_count[max_index]) max_index = i;
43 }
44
45 return max_index;
46}