資訊專欄INFORMATION COLUMN
摘要：思路這道題就是要找區(qū)間之間是否有。而的復(fù)雜度是，所以最后總的復(fù)雜度為。思路的條件依然是不同的是這題需要求房間數(shù)。還是先，指向之前有的最小的那一個(gè)。接著的是，比小，所以又放入。。的是，比大，因此出，放入。。
Meeting Rooms
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.
思路
這道題就是要找區(qū)間之間是否有overlap。對(duì)一個(gè)區(qū)間來說被別的區(qū)間overlap有三種情況：
完全覆蓋：比如[5, 6]和[3, 7]，區(qū)間[5, 6]完全被[3, 7]覆蓋
前一部分被覆蓋：比如[5, 7]和[3, 6]，區(qū)間[5, 7]的前面一部分被[3, 6]覆蓋
后一部分被覆蓋：比如[5, 8]和[7, 9]
不管是哪種，都滿足條件intervals[i].end > intervals[j].start
Sort
直接兩兩比較時(shí)間復(fù)雜度是O(N^2)。為了降低復(fù)雜度，可以先sort一下intervals，根據(jù)start來sort，這樣j就變成i+1，比較的復(fù)雜度變成O(N)。而sort的復(fù)雜度是O(NlogN)，所以最后總的復(fù)雜度為O(NlogN)。java8里面sort可以用lambada表達(dá)式寫。
public boolean canAttendMeetings(Interval[] intervals) {
// base case
if(intervals == null || intervals.length == 0) return true;
// sort
Arrays.sort(intervals, (a, b) -> a.start == b.start ? a.end - b.end : a.start - b.start);
for(int i = 0; i < intervals.length - 1; i++) {
if(intervals[i].end > intervals[i+1].start) return false;
}
return true;
}
Meeting Rooms II
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.
思路
overlap的條件依然是：intervals[i].end > intervals[j].start
不同的是這題需要求房間數(shù)。還是先sort，i指向之前有overlap的最小end的那一個(gè)。
復(fù)雜度
Time Complexity: O(NlogN)，Space: O(N)。
heap
因?yàn)橐乐坝衞verlap的最小的end，所以可以用一個(gè)min heap。每次檢查新的start是否比heap的top元素小，是的話就把保存原來的end，同時(shí)放進(jìn)新的end；否則就放新的end同時(shí)poll出原來的，因?yàn)闆]有overlap且新的end較大。最后heap的大小就是需要的房間數(shù)。比如：
[1, 5], [2, 4], [3, 6], [5, 7]
heap: [5]。[2, 4]的start是2，比5小，所以放入4。
heap: [4, 5]。接著[3 ,6]的start是3，比4小，所以又放入6。
heap: [4, 5, 6]。[5, 7]的start是5，比4大，因此poll出4，放入7。
heap: [5, 6, 7]。最后heap的size為3。
4被pop出來是因?yàn)閇2, 4]和[5, 7]公用一個(gè)房間，只要放7進(jìn)去就可以了。
public int minMeetingRooms(Interval[] intervals) {
// base case
if(intervals == null || intervals.length == 0) return 0;
// sort
Arrays.sort(intervals, (a, b) -> a.start == b.start ? a.end - b.end : a.start - b.start);
// min heap to store the end
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.offer(intervals[0].end);
for(int i = 1; i < intervals.length; i++) {
// no overlap
if(minHeap.peek() <= intervals[i].start) minHeap.poll();
minHeap.offer(intervals[i].end);
}
return minHeap.size();
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66479.html
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,...
摘要：排序法復(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...
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],[...
摘要：泛化泛化數(shù)據(jù)集實(shí)驗(yàn)泛化過擬合的風(fēng)險(xiǎn)泛化泛化能力是指機(jī)器學(xué)習(xí)算法對(duì)新鮮樣本的適應(yīng)能力。機(jī)器學(xué)習(xí)的基本沖突是適當(dāng)擬合我們的數(shù)據(jù)，但也要盡可能簡單地?cái)M合數(shù)據(jù)。使用測試集再次檢查該模型。特征通常在正常范圍內(nèi)，其中第百分位數(shù)的值約為。 泛化&泛化數(shù)據(jù)集&實(shí)驗(yàn) 泛化 (Generalization)：過擬合的風(fēng)險(xiǎn) 泛化:泛化能力（generalization ability）是指機(jī)器學(xué)習(xí)算法對(duì)新...
摘要：題目鏈接這道題感覺是那道的簡化版，思路都是一樣的。是把所有的點(diǎn)都先放到里面，然后一起遍歷。這種寫法的好處是保證了每個(gè)點(diǎn)都只被放進(jìn)一次，不會(huì)重復(fù)遍歷。保證了時(shí)間復(fù)雜是。可以不寫成層次遍歷的形式，直接，的程序 Walls and Gates 題目鏈接：https://leetcode.com/problems... 這道題感覺是那道Shortest Distance from All Bu...
閱讀 3356·2021-11-10 11:36
閱讀 3252·2021-10-08 10:21
閱讀 2889·2021-09-29 09:35
閱讀 2432·2021-09-22 16:06
閱讀 3994·2021-09-09 09:33
閱讀 1341·2019-08-30 15:44
閱讀 3183·2019-08-30 10:59
閱讀 2994·2019-08-29 15:32
