并查集机器调度问题

万千只cnm

这题目啥意思
a是最晚截止时间吗
怎么对"包含当前时间段a和a-1的等价类进行合并”呢

人造人

1. 对于每个任务，确定一个空闲时间段
   
2. 这句话的意思是 要你计算出这个任务在哪个时间执行
   
3. 是时间 0 开始执行吗？
   
4. 是时间 1 开始执行吗？
   
5. 是时间 2 开始执行吗？
   
6. 是时间 3 开始执行吗？
   
7. 是时间 4 开始执行吗？
   
8. 
   
9. 这个时间段在截止时间之前，但与截止时间最接近
   
10. 这句话是这个意思
    
11. 确定当前要开始执行的任务
    
12. 当前时间是 0
    
13. 先看开始时间
    
14. A B C D 中
    
15. 只有 A 和 B 可以开始执行
    
16. 然后再看截止时间
    
17. A 和 B 的截止时间一样，随便选一个，就选 A 了
    
18. 
    
19. 当前时间是 1
    
20. 还有 B C D 三个任务
    
21. 先看开始时间
    
22. 只有 B 和 C 可以开始执行
    
23. 然后再看截止时间
    
24. B 的截止时间是 4
    
25. C 的截止时间是 2
    
26. 当前时间是 1
    
27. 1 离 2 最近
    
28. 选 C
    
29. 与截止时间最接近
    
30. 选当前时间和截止时间之间，离截止时间最近的
    
31. 
    
32. 我想不到这个问题如何用并查集解决
    
33. 下面是一个没有使用并查集的解决方法
    
34. #include <iostream>
    
35. #include <vector>
    
36. #include <algorithm>
    
37. 
    
38. using task_t = std::pair<char, std::pair<size_t, size_t>>;
    
39. 
    
40. std::vector<task_t> get_ready_tasks(const std::vector<task_t> &tasks, size_t current_time) {
    
41.     std::vector<task_t> v;
    
42.     for(const auto &i: tasks) {
    
43.         if(i.second.first <= current_time) {
    
44.             v.push_back(i);
    
45.         }
    
46.     }
    
47.     return v;
    
48. }
    
49. 
    
50. task_t alloc_task(const std::vector<task_t> &tasks, size_t current_time) {
    
51.     std::vector<task_t> ready_tasks = get_ready_tasks(tasks, current_time);
    
52.     if(ready_tasks.empty()) return {0, {0, 0}};
    
53.     sort(ready_tasks.begin(), ready_tasks.end(), \
    
54.             [](const task_t &a, const task_t &b){return a.second.second < b.second.second;});
    
55.     return ready_tasks[0];
    
56. }
    
57. 
    
58. void delete_task(std::vector<task_t> &tasks, char name) {
    
59.     for(size_t i = 0; i < tasks.size(); ++i) {
    
60.         if(tasks[i].first == name) {
    
61.             tasks.erase(tasks.begin() + i);
    
62.         }
    
63.     }
    
64. }
    
65. 
    
66. int main() {
    
67.     std::vector<task_t> tasks = {
    
68.         {'A', {0, 4}},
    
69.         {'B', {0, 4}},
    
70.         {'C', {1, 2}},
    
71.         {'D', {2, 3}}
    
72.     };
    
73.     for(size_t i = 0; tasks.size(); ++i) {
    
74.         task_t task = alloc_task(tasks, i);
    
75.         delete_task(tasks, task.first);
    
76.         if(task.first != 0) std::cout << task.first << std::endl;
    
77.         else std::cout << "(null)" << std::endl;
    
78.     }
    
79.     return 0;
    
80. }
    

复制代码