0253. Meeting Rooms II
https://leetcode.com/problems/meeting-rooms-ii
Description
Given an array of meeting time intervals intervals
where intervals[i] = [starti, endi]
, return the minimum number of conference rooms required.
Example 1:
**Input:** intervals = [[0,30],[5,10],[15,20]]
**Output:** 2
Example 2:
**Input:** intervals = [[7,10],[2,4]]
**Output:** 1
Constraints:
1 <= intervals.length <= 104
0 <= starti < endi <= 106
ac1: priority queue
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;
}
}
Last updated
Was this helpful?