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

一道算法题，真是抓破脑皮：
給你m个meeting（meeting id， start时间，end 时间，priority） 和n个rooms，要求安排尽量多的的meetings， 但是高优先级要优先考虑，即使2个低priority换一个高priority也不行！输入是m，n和好多个string，一个string包含meeting id， start时间，end 时间，priority。 返回安排进去了n个room里面的meeting 的id（按顺序）

for example：
INPUT:
3（# of rooms)
5(# of meetings)
1, 1300, 1400, 100(priority) "meeting 1"
2, 1345, 1445, 100, " meeting 2"
3, 1330， 1350，100 ，“meeting 3”
4，1500， 1700, 75，”meeting 4“
5， 1300,1400,90，”meeting 5“

OUTPUT：
1 3 2 4 （会议的序列）。

现在我想到的方法是：
先根据priority sort，然后在每一个相同priority里再根据结束时间sort。 在从上到下往房间里排，一个房间不行换下一个，如果有compatible的时间，只能drop这个meeting，继续序列里下一个。

这个方法开始我觉得没有问题。但是后来想了很久又发现有问题
比如， 3 个room，meeting如下
priority 100：
----------
      ------------
      ------------
      ------------
priority 90：
----
----
----

这个例子，如果按照我之前说的greedy，会安排如2*90 + 3*100 5个meeting
----------
----  ------------
----  ------------
但是如如果把第一个100 priority的换成另一个，就能把剩下的90 priority 也安排景进去，相当于多了一个90 priority的meeting！！：
----  ------------
----  ------------
----  ------------

所以，高priority同样数量，不同排法肯能影响后面低priority的结果， 有没有办法排高priority是低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大）

readman 发表于 2015-8-1 22:17
- - 仔细看了一下, 发现原来是最简单的带权js问题. 搜下weighted job schxxxxxling problem把...

不是吧， 100 priority有4个，但是我的意思是room只有三个， 所以100priority的不管怎么样都只能有三个，问题是greedy怎么能够得到跟多的90 priority。 恩，看来是我的表达不是很清楚。

readman 发表于 2015-8-1 22:17
首先, 我不明白什么是高优先级要优先考虑. 这个有歧义的.
应该是在xxxx的情况下, 高优先级要优先考虑

就是如果有空间给高优先级的放下，不管这个高优先级占用掉的空间够多少个低优先级放，都先放这个高优先级的。高优先级的没得放再考虑低优先级。

现在想到的 笨方法是
当高优先级 排列 可能出现 相同结果的 多种 set 组合时  把 每种情况都 列出来
再 依次 向 低优先级  用同样的 办法 罗列。。。

好像另一个版块讨论过了吧？
我想了个很麻烦的线段树解法，其他人想出了比较简洁的排序+贪心的做法。
楼主可以搜一下帖子，就是同一个问题吧。

zhuli19901106 发表于 2015-8-1 21:56
好像另一个版块讨论过了吧？
我想了个很麻烦的线段树解法，其他人想出了比较简洁的排序+贪心的做法。
楼 ...

恩，看过帖子。我想到的方法就跟你说的排序贪心算法一样的。当时有问题。就如我举得例子。

larry_cn 发表于 2015-8-1 20:47
现在想到的 笨方法是
当高优先级 排列 可能出现 相同结果的 多种 set 组合时  把 每种情况都 列出来
再  ...

恩，感觉只会brute force了

首先, 我不明白什么是高优先级要优先考虑. 这个有歧义的.
应该是在xxxx的情况下, 高优先级要优先考虑

- - 仔细看了一下, 发现原来是最简单的带权js问题. 搜下weighted job schxxxxxling problem把...

这道题lz会做了吗？感觉好难啊。。。