253 Meeting Rooms II

Search…

253. Meeting Rooms II​
1. Question
Given an array of meeting time intervals consisting of start and end times[[s1,e1],[s2,e2],...](si< ei), find the minimum number of conference rooms required.
For example,
Given[[0, 30],[5, 10],[15, 20]],
return2.
2. Implementation
(1) Heap
思路: 这题的本质是问重复的区间有多少个，建立最小堆存放每个interval的结束时间，扫一遍intervals数组，如果最小堆的堆顶代表的时间点小于或等于当前intervals的开始时间，说明有区间不和当前开始时间代表的区间重复，则最小堆删除堆顶。最后看堆的大小判断最少需要多少个meeting rooms
1
/**
2
 * Definition for an interval.
3
 * public class Interval {
4
 *     int start;
5
 *     int end;
6
 *     Interval() { start = 0; end = 0; }
7
 *     Interval(int s, int e) { start = s; end = e; }
8
 * }
9
 */
10
class Solution {
11
    public int minMeetingRooms(Interval[] intervals) {
12
        if (intervals == null || intervals.length == 0) {
13
            return 0;
14
        }
15
​
16
        Arrays.sort(intervals, (a,b) -> (a.start - b.start));
17
​
18
        PriorityQueue<Integer> endTime = new PriorityQueue<>();
19
        endTime.add(intervals[0].end);
20
​
21
        for (int i = 1; i < intervals.length; i++) {
22
            if (endTime.size() > 0 && endTime.peek() <= intervals[i].start) {
23
                endTime.remove();
24
            }
25
            endTime.add(intervals[i].end);
26
        }
27
        return endTime.size();
28
    }
29
}
Copied!
3. Time & Space Complexity
Heap: 时间复杂度: O(nlogn)， 空间复杂度O(n)

239 Sliding Window Maximum

264 Ugly Number II

Last modified 2yr ago

Copy link

Contents

253. Meeting Rooms II

1. Question

2. Implementation

3. Time & Space Complexity

253. Meeting Rooms II​

1. Question

2. Implementation

3. Time & Space Complexity

253. Meeting Rooms II