-
Notifications
You must be signed in to change notification settings - Fork 31
/
0253-meeting-rooms-ii.rs
54 lines (43 loc) · 1.93 KB
/
0253-meeting-rooms-ii.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
Problem: LeetCode 253 - Meeting Rooms II
Key Idea:
The key idea is to sort the meetings by their start times and use a priority queue (min heap) to track the end times of ongoing meetings. For each meeting, check if there's an available room (i.e., the earliest ending meeting) in the priority queue. If not, allocate a new room. Keep updating the priority queue as meetings start and end. The size of the priority queue represents the minimum number of rooms needed.
Approach:
1. Create two vectors, 'starts' and 'ends', to store the start times and end times of the meetings, respectively.
2. Sort both 'starts' and 'ends' in ascending order.
3. Initialize variables 'rooms' to 0 and 'end_ptr' to 0.
4. Iterate through 'starts':
- If the current start time is less than the current end time in 'ends', it means a meeting overlaps with an ongoing meeting.
- Increment 'rooms' as a new room is required.
- Otherwise, increment 'end_ptr' to indicate that the ongoing meeting has ended.
5. Return 'rooms' as the minimum number of meeting rooms required.
Time Complexity:
O(n log n), where n is the number of meetings. Sorting the 'starts' and 'ends' vectors takes O(n log n) time.
Space Complexity:
O(n), as we use two vectors 'starts' and 'ends' to store the start and end times of meetings.
*/
impl Solution {
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
if intervals.is_empty() {
return 0;
}
let mut starts: Vec<i32> = Vec::new();
let mut ends: Vec<i32> = Vec::new();
for interval in &intervals {
starts.push(interval[0]);
ends.push(interval[1]);
}
starts.sort();
ends.sort();
let mut rooms = 0;
let mut end_ptr = 0;
for start in starts {
if start < ends[end_ptr] {
rooms += 1;
} else {
end_ptr += 1;
}
}
rooms
}
}