0253. Meeting Rooms II
Last updated
Was this helpful?
Last updated
Was this helpful?
Was this helpful?
https://leetcode.com/problems/meeting-rooms-ii
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
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
扫描线
/**
* 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;
}
}