Java (Referred to this post):
Key idea: treat the start and end times individually. 开始时间和结束时间分别做排序。
Time = O(nlogn) sorting takes O(nlogn) time
Space = O(n) two arrays takes O(n) space
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
// Separate out the start times and the end times in their separate arrays.
int[] start = new int[intervals.length];
int[] end = new int[intervals.length];
// Sort the start times and the end times separately.
for (int i = 0; i < intervals.length; i++) {
start[i] = intervals[i][0];
end[i] = intervals[i][1];
}
Arrays.sort(start);
Arrays.sort(end);
int rooms = 0;
int endIndex = 0; // the end pointer helps us track if a meeting has ended and if we can reuse a room.
for (int i = 0; i < intervals.length; i++) { // iterates over all the meetings
if (start[i] < end[endIndex]) {
// 这个meeting的开始时间<当前meeting结束时间，meeting room +1
rooms ++;
} else {
// 这个meeting开始上一个meeting已经结束，不需要新meeting room (reuse)，结束时间index往前移一个
endIndex ++;
}
}
return rooms;
}
}
Python:
# Definition for an interval.
# class Interval:
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution:
def minMeetingRooms(self, intervals: 'List[Interval]') -> 'int':
if not intervals or len(intervals) == 0:
return 0
intervals = sorted(intervals, key = lambda x : x.start)
ends = [intervals[0].end]
num = 1
for i in range(1, len(intervals)):
start = intervals[i].start
if start < min(ends):
num += 1
ends.append(intervals[i].end)
else:
ends.remove(min(ends))
ends.append(intervals[i].end)
return num
Referred to this post
Time = O(nlogn) both sorting and minHeap extract-min operation takes O(n) time
Space = O(n) minHeap takes O(n) space
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
// Sort the intervals by start time
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare (int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// Use a min heap to track the minimum end time of merged intervals
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(intervals.length, new Comparator<int[]>() {
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
// start with the first meeting, put it to a meeting room
pq.offer(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
// get the meeting room that finishes earliest
int[] interval = pq.poll();
if (intervals[i][0] >= interval[1]) {
// if the current meeting starts right after
// there's no need for a new room, merge the interval
interval[1] = intervals[i][1];
} else {
// otherwise, this meeting needs a new room
pq.offer(intervals[i]);
}
// don't forget to put the meeting room back
pq.offer(interval);
}
return pq.size();
}
}