活動選擇。做這件事的最佳方式是什麼

Question

我已經得到了一份會談清單（技術會議）及其各自的會期，我必須以這樣的方式組織這些會談，以至少浪費時間。

他們沒有任何談話的開始時間和結束時間，並且每個談話都與任何談話中的他人無關，可以隨時發生。

上午會議開始於上午9:00和12結束：PM（午餐） 中午會話開始時間下午1:00後和結束於4：PM

什麼，我一直在做到目前爲止我按時間降序排列會議，並將它們放入會議1中。

它的工作原理與我預期的一樣，但我不確定這是否是最佳方式。 任何想法，我還可以做什麼或在某個方向思考？

Answer 1

這是一個多重揹包問題的實例，您描述的算法（貪婪算法）並不總是產生最佳結果。

作爲一個簡單的例子，假設你只有一個會話，3個小時可用。有四次會談，一次持續2.5小時，其餘一次1小時。你的算法將選擇第一次談話，而沒有其他任何空間，給予半小時的停機時間。但最佳的解決方案當然是選擇三個1小時的會談，從而實現零停機時間。

與普通揹包問題不同，多揹包問題與我所知道的很相似。以下是一些可能會提供一些信息的PDF（link），但我會對此答案進行維基百科，任何有簡明扼要答案的人都可以隨意編輯。