贪心算法中常见的区间调度问题
本帖最后由 hongchh 于 2016-8-16 17:27 编辑1. 单区间调度问题
问题定义：存在单一资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, …, req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，求出这组请求的最大相容子集(最优子集)。举个例子：有一间多媒体课室，某一个周末有多个社团想要申请这间课室去举办社团活动，每个社团都有一个对应的申请时间段，比如周六上午8:00-10:00。求出这间课室在这个周末最多能满足几个社团的需求。
2. 多区间调度问题
问题定义：存在多个(或者无限多个)相同的资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, …, req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，用尽可能少的资源满足所有请求(求最优资源数量)。举个例子：有很多间课室，某个周末有多个社团需要申请课室办活动，每个社团都有一个对应的申请时间，求最少需要多少间课室才能够满足所有社团的需求(在这个问题之中时间重叠的社团需要安排在其他课室，即会使用到多个资源，需要考虑多个资源上的调度安排，故称为多区间调度)。
3. 最小延迟调度问题
问题定义：存在单一资源和一组资源请求reqs={req-1, req-2, …, req-n}，与前面两个问题不同，这里的资源从时刻0开始有效(开始接受申请，开始可以被使用)，每个请求req-i都有一个截止时间ddl(i)，每个请求都要占用资源一段连续的时间来完成任务，占用时间为time(i)。每个请求都希望自己能在ddl之前完成任务，不同需求必须被分在不重叠的时间区间(单一资源，同一时刻只能满足一个请求)。假设我们计划满足每个请求，但是允许某些请求延迟(即某个请求在ddl之后完成，延误工期)，确定一种合理的安排，使得所有请求的延期时间中的最大值，是所有可能的时间安排情况中最小的。从时刻0开始，为每个请求req-i分配一个长度time(i)的时间区间，把区间标记为，其中end(i) = begin(i) + time(i)。如果end(i) > ddl(i)，则请求req-i被延迟，延迟时间为delay(i) = end(i) - ddl(i)；否则delay(i) = 0。合理安排需求，使得maxDelay = max{delay(1), delay(2), …, delay(n)}是所有可能的安排中最小的。
解决算法的详细介绍请参考下面博客{:5_91:}
博客地址：http://blog.csdn.net/hongchh/article/details/52183614 能不能写一个python代码让我学习一下啊
页:
[1]