并查集机器调度问题
这题目啥意思a是最晚截止时间吗
怎么对"包含当前时间段a和a-1的等价类进行合并”呢 对于每个任务，确定一个空闲时间段
这句话的意思是 要你计算出这个任务在哪个时间执行
是时间 0 开始执行吗？
是时间 1 开始执行吗？
是时间 2 开始执行吗？
是时间 3 开始执行吗？
是时间 4 开始执行吗？
这个时间段在截止时间之前，但与截止时间最接近
这句话是这个意思
确定当前要开始执行的任务
当前时间是 0
先看开始时间
A B C D 中
只有 A 和 B 可以开始执行
然后再看截止时间
A 和 B 的截止时间一样，随便选一个，就选 A 了
当前时间是 1
还有 B C D 三个任务
先看开始时间
只有 B 和 C 可以开始执行
然后再看截止时间
B 的截止时间是 4
C 的截止时间是 2
当前时间是 1
1 离 2 最近
选 C
与截止时间最接近
选当前时间和截止时间之间，离截止时间最近的
我想不到这个问题如何用并查集解决
下面是一个没有使用并查集的解决方法
#include <iostream>
#include <vector>
#include <algorithm>
using task_t = std::pair<char, std::pair<size_t, size_t>>;
std::vector<task_t> get_ready_tasks(const std::vector<task_t> &tasks, size_t current_time) {
std::vector<task_t> v;
for(const auto &i: tasks) {
if(i.second.first <= current_time) {
v.push_back(i);
}
}
return v;
}
task_t alloc_task(const std::vector<task_t> &tasks, size_t current_time) {
std::vector<task_t> ready_tasks = get_ready_tasks(tasks, current_time);
if(ready_tasks.empty()) return {0, {0, 0}};
sort(ready_tasks.begin(), ready_tasks.end(), \
[](const task_t &a, const task_t &b){return a.second.second < b.second.second;});
return ready_tasks;
}
void delete_task(std::vector<task_t> &tasks, char name) {
for(size_t i = 0; i < tasks.size(); ++i) {
if(tasks.first == name) {
tasks.erase(tasks.begin() + i);
}
}
}
int main() {
std::vector<task_t> tasks = {
{'A', {0, 4}},
{'B', {0, 4}},
{'C', {1, 2}},
{'D', {2, 3}}
};
for(size_t i = 0; tasks.size(); ++i) {
task_t task = alloc_task(tasks, i);
delete_task(tasks, task.first);
if(task.first != 0) std::cout << task.first << std::endl;
else std::cout << "(null)" << std::endl;
}
return 0;
}
页:
[1]