253 Meeting Rooms II
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
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (a,b) -> (a.start - b.start));
PriorityQueue<Integer> endTime = new PriorityQueue<>();
endTime.add(intervals[0].end);
for (int i = 1; i < intervals.length; i++) {
if (endTime.size() > 0 && endTime.peek() <= intervals[i].start) {
endTime.remove();
}
endTime.add(intervals[i].end);
}
return endTime.size();
}
}
3. Time & Space Complexity
Heap: 时间复杂度: O(nlogn), 空间复杂度O(n)
Last updated
Was this helpful?