how to initialize priority queue: PriorityQueue<Interval> pq = new PriorityQueue<Interval>((Interval i1, Interval i2) -> {return i1.end - i2.end;});
/**
* 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; }
* }
*/
// min heap/priority queue
class Solution {
public int minMeetingRooms(Interval[] intervals) {
// edge cases
if (intervals.length == 0) return 0;
PriorityQueue<Interval> pq = new PriorityQueue<Interval>((Interval i1, Interval i2) -> {return i1.end - i2.end;});
Arrays.sort(intervals, (Interval i1, Interval i2) -> {return i1.start - i2.start;});
pq.offer(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
Interval newM = intervals[i];
Interval oldM = pq.poll();
if (newM.start < oldM.end) {
pq.offer(newM);
} else {
oldM.end = newM.end;
}
pq.offer(oldM);
}
return pq.size();
}
}
/**
priority queue, sort by end time
intervals, sort by begin time
new meeting -> check queue -> if start time < end time, new room; else extend then end time.
**/
ac2:
扫描线
/**
* 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) {
// edge cases
if (intervals == null || intervals.length == 0) return 0;
// get start/end points
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
}
// sort for future use
Arrays.sort(starts);
Arrays.sort(ends);
// iterate
int room = 0;
for (int s = 0, e = 0; s < starts.length; s++) {
if (starts[s] < ends[e]) {
room++;
} else {
e++;
}
}
return room;
}
}