Tong's Blog

Welcome to my Blog

0%

大疆笔试：加权区间调度

发表于 更新于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

加权任务区间调度

题目描述：

有一批任务需要调度执行，每个任务的权重为w，开始时间为s，结束时间为f，只有当两个任务的执行时间区间没有重叠的情况，这两个任务才能调度先后执行，否则只能选其中一个执行。

任务：编写一个schedule函数，输入一个有n个任务信息的数组[[wi, si, fi]] 索引 i = 0 …… n-1.返回可调度的最优任务子集（该任务子集的权重和最大）对应的任务索引，输出的索引按照升序进行排列，假设最优子集组合只有一种。

例如：如果两个任务为[10 2 5]和[9 5 7]，则这两个任务执行没有重叠。如果两个任务为[10 2 5]和[9 4 7]，则这两个任务存在重叠区间。

输入：一个n*3的二维数组，n表示n个任务的权重、起始时间和终止时间

输出：一个一维数组，列出最大权重和所对应的任务索引（升序排列）

1
2
3
4
5
6
7
8
9
10
11
12
样例输入：
8 3
3 0 6
1 1 4
4 3 5
17 3 8
9 4 7
10 5 9
8 6 10
1 8 11
样例输出：
3 7

解析：

动态规划求解思路

将任务按照结束时间升序排列，需要用一个数组p[j], 记录与任务j相兼容的最近（最大下标）的任务，如下图中，p[8] = 1, p[7] = 3, p[2] = 0. 设置数组p[j]的目的是方便动态规划推导过程中的区间回退。如果当前区间采用，则向前推到最近的一个不重叠的区间号。

在这里插入图片描述

利用dp数组记录最大权重和，dp数组的含义为：dp[i] 为对于只含有1，2…… i （前i个任务）的可相互兼容的子集的最大权重值。注意，每个区间只有取或者不取这两种状态。为了方便计算，dp数组的长度为n+1, dp[0] = 0. p数组的长度n+1。

动态规划递推过程：

  • 如果dp[i]不选择执行任务i，那么它一定是前i-1个任务的最优解，即dp[i-1]；
  • 如果dp[i]选择执行任务i，那么它是前p[i]个任务的最优解，加上当前任务的权重wi，即dp[p[i]] + wi。

综上递推式为，dp[i] = max(dp[i-1], dp[p[i]] + wi), i > 0; dp[0] = 0;

求出最大权重和，还需求出原始数组中需要执行的任务索引，因为在进行按照结束时间排序后，顺序打乱了，因此需要一个哈希表记录每一个任务信息对应的原始任务索引值，key设置为string类型，value为int类型，si = “wi”+”si”+”fi”; map[si] = i;

根据求得的dp数组，需要找出最大权重和对应的子集区间是哪些，这里从dp数组倒序进行遍历，设置最大权重和为maxVal，如果一个位置k > 0的dp[k] == maxVal && dp[k-1] != maxVal; 说明排序后的第k个区间是执行的，因此存储k区间信息对应的原始索引值，更新maxVal值减去排序后的第k个任务的权重，maxVal -= wk; 或者向前找区间k最近的可执行区间p[k]，将maxVal更新为dp[p[k]].(个人推荐后一种更新maxVal的方法，减少运算合理利用p数组)。

整理代码：

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
using namespace std;

class solution {
public:
    // 注意，比较函数不能直接写在类内部，需加上static静态函数，否则类外调用sort无法访问cmp函数
    // 或者将cmp函数写在类的外部，以及用lambda表达式[&](int& a,int& b){return a < b;}
    static bool cmp(vector<int>& a, vector<int>& b) {
        // 比较两个任务信息数组，按照结束时间进行升序排序
        return a[2] < b[2];
    }
    
    // 辅助函数 将任务信息数组转化为string类型便于哈希表存储
    string help(vector<int> arr) {
        string s;
        for (auto a : arr) {
            s += to_string(a);
        }
        return s;
    }
    // 主函数
    vector<int> schedule(vector<vector<int>> arr) {
        int n = arr.size();
        unordered_map<string, int> mp;
        // 哈希表存储任务信息列表对应的原始索引值
        for (int i = 0; i < n; i++) {
            mp.insert(make_pair(help(arr[i]), i));
        }
		
        // 便于计算，这里插入一个0进程的调度信息，这样排序后的第i个任务就是arr[i]
        arr.push_back({0, 0, 0});
        // 按照结束时间进行升序排序
        sort(arr.begin(), arr.end(), cmp);
        
        // 辅助数组p，记录当前区间之前，最近的一个不重叠区间的位置
        vector<int> p(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            for (int j = i-1; j > 0; j--) {
                if (arr[j][2] <= arr[i][1]) {
                    p[i] = j;
                    break;
                }
            }
        }

        vector<int> res; // 记录结果
        
        vector<int> dp(n + 1, 0);// dp数组，记录当前i个区间的最优解，dp[i]为当前的最大权重和
        dp[0] = 0;
        
        // dp递推关系
        for (int i = 1; i <= n; i++) {
            if (dp[p[i]] + arr[i][0] >= dp[i-1]) { // 执行第i个区间
                dp[i] = dp[p[i]] + arr[i][0];
                
            } else { // 不执行第i个区间
                dp[i] = dp[i - 1];
                
            }
        }
        
        int maxVal = dp[n]; // 区间n的最大权重和
        int index = 0;
        // 倒序遍历dp数组
        for (int i = n; i > 0; i--) {
            // 找到执行的区间位置
            if (dp[i] == maxVal && dp[i - 1] != maxVal) {
                index = i;
                res.push_back(mp[help(arr[index])]);
                maxVal = dp[p[index]];
                //maxVal -= arr[index][0];
            } 
        }
        
        sort(res.begin(), res.end()); // 注意结果要求升序排序
        
        return res;
    }
};

int main() {
    int n, num;
    cin >> n >> num;
    vector<vector<int>> arr(n);
    int len  = n;
    int wi = 0, si = 0, fi = 0;
    while (n--) {
        cin >> wi >> si >> fi;
        arr[len - n - 1].push_back(wi);
        arr[len - n - 1].push_back(si);
        arr[len - n - 1].push_back(fi);    
    }
    /*
    arr1 = {{2,0,4}, {4,1,6}, {4,5,7}, {7,2,9}, {2,8,10}, {1,8,11}};
    输出：0 2 4
    arr2 = {{3,0,6},{1,1,4},{4,3,5},{17,3,8},{9,4,7},{10,5,9},{8,6,10},{1,8,11}};
    输出：3 7
    */
    vector<int> res;
    solution test;
    res = test.schedule(arr);
    for (auto& v : res) {
        cout << v << " ";
    }
    return 0;
}