資訊專欄INFORMATION COLUMN
Problem
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
class Solution {
public int minMeetingRooms(Interval[] intervals) {
//0, 100 ---- 1
//0, 200 ---- 2
//0, 300 ---- 3
//150, 250 -- 3
//160, 260 -- 4
//210, 310 -- 4
int n = intervals.length;
int[] startTimes = new int[n];
int[] endTimes = new int[n];
for (int i = 0; i < n; i++) {
startTimes[i] = intervals[i].start;
endTimes[i] = intervals[i].end;
}
Arrays.sort(startTimes);
Arrays.sort(endTimes);
int count = 0;
int i = 0, j = 0;
while (i < n && j < n) {
//once overlaps, room++
if (startTimes[i] < endTimes[j]) count++;
//not overlapping, release prev meeting room
else j++;
i++;
}
return count;
}
}
Using Heap
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return 0;
Arrays.sort(intervals, (a, b) -> a.start-b.start);
PriorityQueue queue = new PriorityQueue<>((a, b) -> a.end-b.end);
/*add room for the first meeting*/
queue.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
Interval pre = queue.poll();
Interval cur = intervals[i];
// if new meeting time overlapped, add a new room for this meeting
if (cur.start < pre.end) queue.offer(cur);
// if not overlapped, no new room for the new meeting,
// just update the ending time for the earliest-to-end room
else pre.end = cur.end;
// put this previous earliest-to-end room back back to heap,
// so that in next iteration, we get the new earliest-to-end room
queue.offer(pre);
}
return queue.size();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77272.html
摘要：排序法復(fù)雜度時(shí)間空間思路這題和很像，我們按開始時(shí)間把這些都給排序后，就挨個(gè)檢查是否有沖突就行了。有沖突的定義是開始時(shí)間小于之前最晚的結(jié)束時(shí)間。這里之前最晚的結(jié)束時(shí)間不一定是上一個(gè)的結(jié)束時(shí)間，所以我們更新的時(shí)候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...
摘要：思路這道題就是要找區(qū)間之間是否有。而的復(fù)雜度是，所以最后總的復(fù)雜度為。思路的條件依然是不同的是這題需要求房間數(shù)。還是先，指向之前有的最小的那一個(gè)。接著的是，比小，所以又放入。。的是，比大，因此出，放入。。 Meeting Rooms Given an array of meeting time intervals consisting of start and end times [[...
Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...
摘要：廣度優(yōu)先搜索復(fù)雜度時(shí)間空間思路實(shí)際上就是找每個(gè)房間到最近的門的距離，我們從每個(gè)門開始，廣度優(yōu)先搜索并記錄層數(shù)就行了。這題要注意剪枝，如果下一步是門或者下一步是墻或者下一步已經(jīng)訪問過了，就不要加入隊(duì)列中。 Walls and Gates You are given a m x n 2D grid initialized with these three possible values....
摘要：為了盡量保證右邊的點(diǎn)向左走，左邊的點(diǎn)向右走，那我們就應(yīng)該去這些點(diǎn)中間的點(diǎn)作為交點(diǎn)。由于是曼哈頓距離，我們可以分開計(jì)算橫坐標(biāo)和縱坐標(biāo)，結(jié)果是一樣的。 Best Meeting Point A group of two or more people wants to meet and minimize the total travel distance. You are given a ...
閱讀 2203·2023-04-25 19:06
閱讀 1408·2021-11-17 09:33
閱讀 1794·2019-08-30 15:53
閱讀 2616·2019-08-30 14:20
閱讀 3576·2019-08-29 12:58
閱讀 3575·2019-08-26 13:27
閱讀 533·2019-08-26 12:23
閱讀 516·2019-08-26 12:22
