a******d 发帖数: 82 | 1 活動資源分配問題,類似不相交區間等經典貪心算法問題。已知不同活動的開始時間和
結束時間,求最少能把這些活動分為多少組使得每組中的活動時間不衝突。實際應用:
活動需要在一個房間中進行,時間上不衝突的活動可以先後使用同一個房間,而問題就
是如何儘量降低房間資源佔用(最小化需要的房間數量)。如有以下活動區間:
[1, 4], [3, 5], [4, 6], [6, 7], [1, 9], [10, 11], [6, 10]
那麼最優解就是分為 3 組,具體的安排可能是 [1, 4], [4, 6], [6, 7], [10, 11]
在一個房間,[3, 5], [6, 10] 在一個房間,[1, 9] 在一個房間。
---------------------
这个题目如何入手?
如果是贪心法, 怎么证明结果是最优的? | e********2 发帖数: 495 | 2 房间数=max overlapping intervals
3个
[1, 4], [3, 5], [1, 9]
【在 a******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 活動資源分配問題,類似不相交區間等經典貪心算法問題。已知不同活動的開始時間和 : 結束時間,求最少能把這些活動分為多少組使得每組中的活動時間不衝突。實際應用: : 活動需要在一個房間中進行,時間上不衝突的活動可以先後使用同一個房間,而問題就 : 是如何儘量降低房間資源佔用(最小化需要的房間數量)。如有以下活動區間: : [1, 4], [3, 5], [4, 6], [6, 7], [1, 9], [10, 11], [6, 10] : 那麼最優解就是分為 3 組,具體的安排可能是 [1, 4], [4, 6], [6, 7], [10, 11] : 在一個房間,[3, 5], [6, 10] 在一個房間,[1, 9] 在一個房間。 : --------------------- : 这个题目如何入手? : 如果是贪心法, 怎么证明结果是最优的?
| w****a 发帖数: 710 | | m****9 发帖数: 492 | 4 你的网站domain 是这样断句的么?f g dsb?
【在 w****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.fgdsb.com/2015/01/08/meeting-rooms/
| w****a 发帖数: 710 | 5 你的聪明让我颤抖。
【在 m****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的网站domain 是这样断句的么?f g dsb?
| a******d 发帖数: 82 | | a******d 发帖数: 82 | 7 一针见血的指导啊
【在 e********2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 房间数=max overlapping intervals : 3个 : [1, 4], [3, 5], [1, 9]
| m****9 发帖数: 492 | 8 嗷嗷嗷
【在 w****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的聪明让我颤抖。
|
|