间隔调度算法或活动选择算法
帕拉格·柳吉
我一直在努力解决这个问题。
有n个人想要在酒店同一个房间。每个人都希望在自己方便的时间停留在酒店内，但一次只能住一个人。假设房间从上午5点到晚上11点可用。酒店经理从那个房间里的每个人那里收取500卢比。一个人在那个房间里待多久都没关系。我们必须最大化经理的利润。让我们说n = 4，即四个人想要同一个房间。假设第一个人想要从上午6点至8点的房间，第二个人想要从上午7点至8AM的房间，第三个人想要从上午8点至12PM的房间，第四个人想要从上午11点至1PM的房间。
通过观察上图，我们可以轻松地看到经理最多只能允许两个人留下（第一和第三或第一和第四或第二和第三或第二和第四）。因此，他可以获得的最大利润是500 + 500 = 1000卢比。因此，我们必须实现可以找到最大利润值的算法。假设人们只想在早上5点至晚上11点左右的房间，而每个人都希望在几个小时内找到房间。
输入说明：
{<第一人称开始时间>＃<第一人称结束时间>，<第二人称开始时间>＃<第二人称结束时间>，…………，＃}
输出说明：
输出应为最大利润值。
对于问题中考虑的示例，输出为2000。
例子：
输入：
{6 AM#8AM、11AM#1PM、7AM#3PM、7AM#10AM、10AM#12PM、2PM#4PM、1PM#4PM、8AM#9AM}
产量：
2000
用户名
看起来像“活动选择问题”的变体。
阅读此《TopCoder教程》以获得出色的解释。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
算法-加权间隔调度问题变体
- 2
贪婪算法的最佳算法：间隔调度-调度所有间隔
- 3
CPU调度程序算法
- 4
作业调度算法
- 5
调度算法的实现
- 6
变型调度算法
- 7
事件的调度算法
- 8
具有两种活动类型的活动选择算法
- 9
间隔树算法的补充
- 10
处理设定间隔的算法
- 11
算法：最长近似间隔
- 12
查找非重叠序列的最大覆盖范围的算法。（即加权间隔调度概率。）
- 13
有限制的调度算法
- 14
简单的最大利润调度算法
- 15
内核使用哪种调度算法？
- 16
在Python中使用贪婪算法进行活动选择
- 17
贪婪算法：间隔着色
- 18
将线分成间隔的算法
- 19
最小间隔对象的算法
- 20
A *算法开放列表选择
- 21
C ++“选择”算法
- 22
矩形选择算法
- 23
了解选择算法
- 24
选择等级算法
- 25
选择/排序算法（背包）
- 26
选择排序算法交换
- 27
Corda 硬币选择算法
- 28
具有I / O的循环（调度）算法
- 29
使用matplotlib可视化调度算法
我来说两句