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 的大作中提到】
: 活動資源分配問題，類似不相交區間等經典貪心算法問題。已知不同活動的開始時間和
: 結束時間，求最少能把這些活動分為多少組使得每組中的活動時間不衝突。實際應用：
: 活動需要在一個房間中進行，時間上不衝突的活動可以先後使用同一個房間，而問題就
: 是如何儘量降低房間資源佔用（最小化需要的房間數量）。如有以下活動區間：
: [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 的大作中提到】
: http://www.fgdsb.com/2015/01/08/meeting-rooms/
| w****a
发帖数: 710 | 5 你的聪明让我颤抖。
【在 m****9 的大作中提到】
: 你的网站domain 是这样断句的么？f g dsb?
| a******d
发帖数: 82 | | a******d
发帖数: 82 | 7 一针见血的指导啊
【在 e********2 的大作中提到】
: 房间数=max overlapping intervals
: 3个
: [1, 4], [3, 5], [1, 9]
| m****9
发帖数: 492 | 8 嗷嗷嗷
【在 w****a 的大作中提到】
: 你的聪明让我颤抖。
|
|
