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.
For example:
- Given
[[0, 30],[5, 10],[15, 20]], - return
2.
C Solution:
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* };
*/
void quick_sort(int *nums, int len) {
if (len < 2) return;
int key = nums[len - 1];
int i;
for (i = 0; i < len - 1 && nums[i] < key; i++);
if (i == len - 1) {
quick_sort(nums, len - 1);
return;
}
int j;
for (j = i + 1; j < len - 1; j++) {
if (nums[j] < key) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i++] = tmp;
}
}
nums[len - 1] = nums[i];
nums[i] = key;
quick_sort(nums, i);
quick_sort(nums + i + 1, len - i - 1);
}
int minMeetingRooms(struct Interval* intervals, int intervalsSize) {
int *start = malloc(intervalsSize * sizeof(int));
int *end = malloc(intervalsSize * sizeof(int));
int i;
for (i = 0; i < intervalsSize; i++) {
start[i] = intervals[i].start;
end[i] = intervals[i].end;
}
quick_sort(start, intervalsSize);
quick_sort(end, intervalsSize);
int room = 0, j = 0;
for (i = 0; i < intervalsSize; i++) {
if (start[i] < end[j]) room++;
else j++;
}
return room;
}
Heap Solution:
Summary:
- Greedy. I am not sure I understand it throughly.
- This problem can be solved with heap, but that's not necessary.
- Heap solution:
- sort the intevals by start.
- build a heap of ends.
- loop through starts, compare with the minimum end, maintain heap.
- This problem is not a good practice for heap.
- 9ms, 66.67%
LeetCode: 253. Meeting Rooms II
近期评论