[LintCode] Problem 919 - Meeting Rooms II

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.

Example

No.1

Input: intervals = [(0,30),(5,10),(15,20)]

Output: 2

Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)

No.2

Input: intervals = [(2,7)]

Output: 1

Explanation:
Only need one meeting room

Code

1
2
3
4
5
6
7
8
public class Interval {
int start, end;

Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minMeetingRooms(List<Interval> intervals) {
if (intervals == null || intervals.size() < 1)
return 0;

Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(intervals.get(0).end);

for (int i = 1; i < intervals.size(); i++) {
if (intervals.get(i).start > minHeap.peek())
minHeap.poll();

minHeap.offer(intervals.get(i).end);
}

return minHeap.size();
}