253. Meeting Rooms II (Medium)
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.
Solution 1: Greedy + minHeap O(n log n); O(n)
If you look at these meetings in a time line one after another (like stream data), then this solution is a greedy solution.
The heap stores all conflicting meetings, which must be resolved by independent rooms. The heap’s head is the meeting that has earliest end time. All other meetings collide with each other mutually in the heap.
When a new meeting comes (this is the reason that we need to sort by start time), we greedily choose the meeting A that finished the earliest (this is the reason that we use minheap on end time). If the new meeting does not collide with A, then the new meeting can re-use A’s room, or simply extend A’s room to the new meeting’s end time.
If the new meeting collides with A, then it must collide with all meetings in the heap. So a new room must be created.
The reason for correctness is the invariant: heap size is always the minimum number of rooms we need so far. If the new meeting collides with everyone, then a new room must be created; if the new meeting does not collide with someone, then it must not collide with the earliest finish one, so greedily choose that one and re-use that room. So the invariant is maintained.
/**
* minHeap O(nlogn);O(n)
* I think we can use the Greedy algorithm, always put the next starting meeting after the first ending meeting.
* If the start time overlaps with the nearest end time, that means we need a new room.
* So, sort the meetings by start time first.
* Then for each interval in the array:
* | If min heap is not empty and start time doesn't overlap with first ending time:
* | Poll first ending time from the heap.
* | Add the ending time for current meeting.
*/
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
// Arrays.sort(intervals, new Comparator<Interval>() {
// public int compare(Interval a, Interval b) {
// return a.start - b.start;
// }
// });
Arrays.sort(intervals, (a, b) -> a.start - b.start);
// PriorityQueue<Interval> heap = new PriorityQueue<>(intervals.length, new Comparator<Interval>() {
// public int compare(Interval a, Interval b) {
// return a.end - b.end;
// }
// });
// heap.offer(intervals[0]);
// for (int i = 1; i < intervals.length; i++) {
// Interval head = heap.poll();
// if (head.end <= intervals[i].start) {
// head.end = intervals[i].end;
// } else {
// heap.offer(intervals[i]);
// }
// }
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (Interval i : intervals) {
if (!heap.isEmpty() && i.start >= heap.peek()) { //non-overlap, which means one room can be reused
heap.poll();最先占用meeting room的intervals的索引么？
}
heap.offer(i.end);
}
return heap.size();
}
Solution 2: two arrays O(n log n); O(n)
Very similar with what we do in real life. Whenever you want to start a meeting, you go and check if any empty room available (available > 0) and if so take one of them ( available -=1 ). Otherwise, you need to find a new room someplace else ( numRooms += 1 ). After you finish the meeting, the room becomes available again ( available += 1 ).
public int minMeetingRoomsB(Interval[] intervals) {
if (intervals == null || intervals.length == 1) {
return 0;
}
int n = intervals.length;
int[] start = new int[n];
int[] end = new int[n];
for (int i = 0; i < n; i++) {
start[i] = intervals[i].start;
end[i] = intervals[i].end;
}
Arrays.sort(start);
Arrays.sort(end);
int rooms = 0;
int reusedRooms = 0;
for (int i = 0; i < n; i++) {
if (start[i] < end[i]) {
rooms++;
} else {
reusedRooms++;
}
}
return rooms;
}
Solution 3: HashMap
public int minMeetingRooms(Interval[] intervals) {
Map<Integer,Integer> map = new TreeMap<>();
for(int i = 0; i < intervals.length; i++){
Interval temp = intervals[i];
map.put(temp.start,map.getOrDefault(temp.start,0)+1);
map.put(temp.end,map.getOrDefault(temp.end,0)-1);
}
int result = 0;
int room = 0;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
room += entry.getValue();
result = Math.max(result,room);
}
return result;
}
Follow Up:
1.返回同时开会的最大房间数（实际就是原题的需要的最小房间数，需要理解下）时时间 return the exact time that has max num of room used (any valid time) 换个马甲：给一个list of intervals,and find the point where maximum intervals overlap. 面试官提示说类似于skyline problem那样用一个stack TODO
public int minMeetingRoomsC(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (a, b) -> a.start - b.start);
int overlapStart = -1;
int overlapEnd = -1;
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (Interval i : intervals) {
if (!heap.isEmpty() && i.start >= heap.peek()) { //non-overlap, which means one room can be reused
heap.poll();
} else {
//代码应该有问题，等开会员后测试一下
overlapStart = i.start;
overlapEnd = Math.min(heap.peek(), i.end);//should be min of these two
}
heap.add(i.end);
}
return overlapStart;
}
2.输出所有meeting room 的id
3.给一个list of intervals,and find the point where maximum intervals overlap. 面试官提示说类似于skyline problem那样用一个stack,但最后也没来得及完全想出来
4.(OfferUp) 求freq最高的时间段