求助求助：interval schedule, n room for most number of meetings with priority

eejchen 发表于 2018-3-3 03:29
这道题lz会做了吗？感觉好难啊。。。

这道题目首先可以做个转换，将priority转为weight，只要保证如下性质：
(1) 相同priority有相同weight
(2) 高priority的weight大于所有比其低的priority的weight之和

然后求最大化weight总和的调度就可以了，算法参见这篇文章：
E. M. Arkin and E. B. Silverberg. 1987. Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18, 1 (November 1987), 1-8.

https://ac.els-cdn.com/0166218X8 ... d9bfd070dc50e546bfe

时间复杂度O(n^2 log(n))


关于转换priority到weight，比如说楼主给的输入：

1. "meeting 1" -- 100 (priority)
   
2. "meeting 2" -- 100
   
3. "meeting 3" -- 100
   
4. "meeting 4" -- 75
   
5. "meeting 5" -- 90

复制代码

那么一个可行转换如下：

1. "meeting 1" -- 4 (weight)
   
2. "meeting 2" -- 4
   
3. "meeting 3" -- 4
   
4. "meeting 4" -- 1
   
5. "meeting 5" -- 2

复制代码

这样算法在最大化weight时，一定会优先高priority（因为所有低priority的weight加起来也没有一个高priority的weight大）

magicsets 发表于 2018-3-3 05:09
这道题目首先可以做个转换，将priority转为weight，只要保证如下性质：
(1) 相同priority有相同weight
...

谢谢这位童鞋的解答！不明觉厉，先看看推荐的文章再说。。。