Amazon
Apple
Bloomberg
Microsoft
Oracle
Roblox
Snapchat
Yandex
eBay
2020-10-30
253. Meeting Rooms II
Similar Question: LeetCode Question 252
Question:
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 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:
Input: [[7,10],[2,4]]
Output: 1
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Solution:
Using the priority queue, check the meeting with earilest ending time. If conflicts, no deque opertation, add a second meeting to the queue. Result is the size of the queue.
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, (int[] a, int[] b) -> (a[0] - b[0]));
PriorityQueue<int[]> pq = new PriorityQueue<>((int[] a, int[] b) -> (a[1] - b[1]));
pq.offer(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= pq.peek()[1]) {
pq.poll();
}
pq.offer(intervals[i]);
}
return pq.size();
}
}
Use two arrays to sort the starting and ending time, if there’s a conflict increase the result.
class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for(int i=0; i<intervals.length; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int result = 0;
int endPointer = 0;
int room = 0;
for(int i=0; i<starts.length; ) {
if(starts[i] < ends[endPointer]) {
room++;
result = Math.max(result, room);
i++;
} else {
endPointer++;
room--;
}
}
return result;
}
}
More concise way to use sort. Think as a bus problem with onboarding and offboarding process. Think the endpointer same as the peek() in prioirtyqueue. A better explanation: https://learnku.com/articles/34713
class Solution {
public int minMeetingRooms(int[][] intervals) {
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for(int i=0; i<intervals.length; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int result = 0;
int endPointer = 0;
int room = 0;
for(int i=0; i<starts.length; i++) {
if(starts[i] < ends[endPointer]) {
room++;
} else {
endPointer++;
}
}
return room;
}
}
Using hashmap to mark the time and travese the time.
class Solution {
public int minMeetingRooms(int[][] intervals) {
Map<Integer, Integer> map = new TreeMap<>();
for (int[] itl : intervals) {
map.put(itl[0], map.getOrDefault(itl[0], 0) + 1);
map.put(itl[1], map.getOrDefault(itl[1], 0) - 1);
}
int room = 0, k = 0;
for (int v : map.values())
k = Math.max(k, room += v);
return k;
}
}