253. Meeting Rooms II
Tags:
Medium
Skills:
min-heapIntervalOverlapping array
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
startPtr và endPtr để duyệt qua danh sách thời gian bắt đầu và thời gian kết thúc.start[startPtr] < end[endPtr]), cần thêm một phòng họp.start[startPtr] >= end[endPtr]), giảm số phòng họp đang sử dụng.Implement
Naive Solution
1function minMeetingRooms(intervals: number[][]): number {
2 /**
3 - Nếu có overlap thì require_room += 1
4 - loop through intervals, check if intervals[i].at(-1) > intervals[i + 1].at(0) -> overlap
5 */
6
7 let requireRoom = 1;
8 intervals.sort((a, b) => a[0] - b[0])
9 for (let i = 0; i < intervals.length - 1; i++) {
10 const interval = intervals[i];
11 const nextInterval = intervals[i + 1]
12
13 if (interval.at(-1) > nextInterval.at(0)) {
14 requireRoom += 1
15 }
16 }
17
18 return requireRoom;
19
20};Solution trên chỉ đúng khi các bạn cần merge interval đối với time. Còn ở problem này yêu cầu chúng mình cần tìm được số room tối thiểu để tổ chức tất cả cuộc họp. Điều đó có nghĩa là có thể sẽ có một cuộc họp khác xảy ra khi một cuộc họp hiện tại đang được bắt đầu và chưa kết thúc
Correct solution
Approach
starts , ends starts[i] < end[j] cần thêm một phòngstarts[i] >= ends[j] ), có thể tái sử dụng phòng, tăng pointerends lênSolution
1function minMeetingRooms(intervals: number[][]): number {
2 if (intervals.length === 0) {
3 return 0;
4 }
5
6 const startTimes = intervals.map(i => i[0]).sort((a, b) => a - b);
7 const endTimes = intervals.map(i => i[1]).sort((a, b) => a - b);
8
9 let rooms = 0;
10 let endPointer = 0;
11
12 for (let i = 0; i < intervals.length; i++) {
13 if (startTimes[i] < endTimes[endPointer]) {
14 rooms++
15 } else {
16 endPointer++
17 }
18 }
19 return rooms
20};Time and space complexity
start_times và end_times: O(nlogn)start_times và end_times với độ dài O(n).Approach - Min Heap
Solution - Min Heap
1function minMeetingRooms(intervals: number[][]): number {
2 if (intervals.length === 0) return 0;
3
4 intervals.sort((a, b) => a[0] - b[0])
5
6 const min_heap = new MinPriorityQueue<number>();
7
8 for (const [start, end] of intervals) {
9 if (!min_heap.isEmpty() && min_heap.front() <= start) {
10 min_heap.dequeue();
11 }
12 min_heap.enqueue(end)
13 }
14
15 return min_heap.size()
16};