未分类

【贪心算法】区间调度问题总结

数据结构与算法

1. 单区间调度问题

问题定义：存在单一资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, ..., req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，求出这组请求的最大相容子集(最优子集)。举个例子：有一间多媒体课室，某一个周末有多个社团想要申请这间课室去举办社团活动，每个社团都有一个对应的申请时间段，比如周六上午8:00-10:00。求出这间课室在这个周末最多能满足几个社团的需求。

解决方案：贪心算法，优先选择最早结束的需求，确保资源尽可能早地被释放，把留下来满足其他需求的时间最大化。具体伪代码如下所示，算法结束后集合A中会保留所有相容请求，A的大小即是最大相容数量。

1
2
3
4
5
6
7
8
初始化R是所有需求的集合，A为空集
对R中的需求Ri，根据结束时间从早到晚排序
for Ri in R, do
  if Ri与A中的请求相容
    A = A并Ri
  endIf
endFor
return A

上述伪代码的C++实现如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
  int begin, end;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
  return req1.end < req2.end;
}

int main() {
  int requestNum;
  cin >> requestNum;
  if (requestNum > MAX_SIZE) {
    cout << "请求数量过多" << endl;
    return 0;
  }
  for (int i = 0; i < requestNum; ++i) {
    cin >> req[i].begin >> req[i].end;
  }

  sort(req, req + requestNum);

  vector<Request> rvec;
  rvec.push_back(req[0]);
  for (int i = 1; i < requestNum; ++i) {
    if (rvec[rvec.size() - 1].end <= req[i].begin) {
      rvec.push_back(req[i]);
    }
  }

  cout << "最大兼容量: " << rvec.size() << endl;
  return 0;
}

2. 多区间调度问题

问题定义：存在多个(或者无限多个)相同的资源，有一组以时间区间形式表示的资源请求reqs={req-1, req-2, ..., req-n}，第i个请求希望占用资源一段时间来完成某些任务，这段时间开始于begin(i)终止于end(i)。如果两个请求req-i和req-j在时间区间上没有重叠，则说这两个请求是相容的，用尽可能少的资源满足所有请求(求最优资源数量)。举个例子：有很多间课室，某个周末有多个社团需要申请课室办活动，每个社团都有一个对应的申请时间，求最少需要多少间课室才能够满足所有社团的需求(在这个问题之中时间重叠的社团需要安排在其他课室，即会使用到多个资源，需要考虑多个资源上的调度安排，故称为多区间调度)。

解决方案：贪心算法，将需求按照开始时间的早晚进行排序，然后开始为这些资源打标签，每个标签代表都一个资源，需求req-i被打上标签k表示该请求分配到的资源是k。遍历排序后的需求，如果一个需求与某个已分配资源上的其他安排不冲突，则把该需求也放进该资源的安排考虑中；如果冲突，那么应该要给此需求分配新的资源，已用资源数量加一。具体操作的伪代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
对n个需求按照开始时间从早到晚进行排序
假设排序后的需求记为{R1, R2, ..., Rn}
初始化tagSize = 1;
for i=1 to n, do:
  tags = {1,2,...,tagSize};
  for j = 1 to i-1, do:
    if Rj与Ri时间区间重叠产生冲突:
      tags = tags - {Rj的标签};
    endIf
  endFor
  if tags为空集:
    tagSize += 1;
    将标签tagSize贴在Ri上
  EndIf
  else:
    在tags剩下的标签中随便挑一个贴给Ri
  endElse
endFor
此时每个请求上都贴有标签，每个标签对应其申请的资源编号，此时的tagSize就是至少需要的资源数量
return tagSize;

上述伪代码的C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
  int begin, end, tag;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
  return req1.begin < req2.begin;
}

int main() {
  int requestNum;
  cin >> requestNum;
  if (requestNum > MAX_SIZE) {
    cout << "请求数量过多" << endl;
    return 0;
  }
  for (int i = 0; i < requestNum; ++i) {
    cin >> req[i].begin >> req[i].end;
  }

  sort(req, req + requestNum);

  int tagSize = 1;
  req[0].tag = 0;
  bool tags[MAX_SIZE];
  for (int i = 1; i < requestNum; ++i) {
    memset(tags, 1, sizeof(tags));
    for (int j = 0; j < i; ++j) {
      if (req[j].end > req[i].begin) {
        tags[req[j].tag] = false;
      }
    }
    bool isTagsEmpty = true;
    int tag;
    for (int j = 0; j < tagSize; ++j) {
      if (tags[j]) {
        isTagsEmpty = false;
        tag = j;
        break;
      }
    }
    if (isTagsEmpty) {
      req[i].tag = tagSize;
      ++tagSize;
    } else {
      req[i].tag = tag;
    }
  }

  cout << "最小资源使用量: " << tagSize << endl;
  return 0;
}

3. 最小延迟调度问题

问题定义：存在单一资源和一组资源请求reqs={req-1, req-2, ..., req-n}，与前面两个问题不同，这里的资源从时刻0开始有效(开始接受申请，开始可以被使用)，每个请求req-i都有一个截止时间ddl(i)，每个请求都要占用资源一段连续的时间来完成任务，占用时间为time(i)。每个请求都希望自己能在ddl之前完成任务，不同需求必须被分在不重叠的时间区间(单一资源，同一时刻只能满足一个请求)。假设我们计划满足每个请求，但是允许某些请求延迟(即某个请求在ddl之后完成，延误工期)，确定一种合理的安排，使得所有请求的延期时间中的最大值，是所有可能的时间安排情况中最小的。从时刻0开始，为每个请求req-i分配一个长度time(i)的时间区间，把区间标记为[begin(i), end(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)}是所有可能的安排中最小的。

解决方案：贪心算法，按照截止时间ddl排序，越早截止的任务越早完成。该算法是一个没有空闲的最优调度，即从时刻0开始都有在处理请求，直到最后一个请求执行完释放资源之后才空闲。伪代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
将需求按照截止时间进行排序
假设排序后的截止时间为ddl[1]<=...<=ddl[n]
start = 0;
maxDelay = 0;
for i = 1 to n, do:
  begin[i] = start;
  end[i] = start + time[i];
  start = end[i] + time[i];
  if maxDelay < end[i] - ddl[i]:
    L = end[i] - ddl[i];
  endIf
endFor
则每个任务安排的时间区间为[begin[i], end[i]]，所有任务中最大的延迟为maxDelay，maxDelay为所有可能的任务安排中最小的延迟
return maxDelay;

上述代码的C++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 100;

struct Request {
  int time, ddl;
  int begin, end;
} req[MAX_SIZE];

bool operator<(const Request& req1, const Request& req2) {
  return req1.ddl < req2.ddl;
}

int main() {
  int requestNum;
  cin >> requestNum;
  if (requestNum > MAX_SIZE) {
    cout << "请求数量过多" << endl;
    return 0;
  }
  for (int i = 0; i < requestNum; ++i) {
    cin >> req[i].time >> req[i].ddl;
  }

  sort(req, req + requestNum);

  int start = 0, maxDelay = 0;
  for (int i = 0; i < requestNum; ++i) {
    req[i].begin = start;
    req[i].end = start + req[i].time;
    start += req[i].time;
    if (maxDelay < req[i].end - req[i].ddl) {
      maxDelay = req[i].end - req[i].ddl;
    }
  }

  cout << "最小的最大延迟: " << maxDelay << endl;
  return 0;
}

分享到