任务最优调度 --- 华为od刷题

题目描述

给定一个正整数数组表示待系统执行的任务列表，数组的每一个元素代表一个任务，元素的值表示该任务的类型。

请计算执行完所有任务所需的最短时间。

任务执行规则如下:

1. 任务可以按任意顺序执行，且每个任务执行耗时间均为1个时间单位。
2. 两个同类型的任务之间必须有长度为N个单位的冷却时间，比如N为2时，在时间K执行了类型3的任务，那么K+1和K+2两个时间不能执行类型3任务。
3. 系统在任何一个单位时间内都可以执行一个任务，或者等待状态。

说明：数组最大长度为1000，速度最大值1000。

输入描述

• 第一行记录一个用半角逗号分隔的数组，数组长度不超过1000，数组元素的值不超过1000，
• 第二行记录任务冷却时间，N为正整数，N<=100。

输出描述

• 输出为执行完所有任务所需的最短时间。

用例

参考

【华为OD机试 】 任务最优调度（C++ Java JavaScript Python）

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main() {
    string input;
    cin >> input; // 输入任务序列，以逗号分隔
    vector<int> tasks; // 定义任务向量
    string num; 
    for (char c : input) { // 遍历输入字符串
        if (c == ',') { // 如果遇到逗号
            tasks.push_back(stoi(num)); // 将当前数字字符串转换为整数并加入任务向量
            num.clear(); // 清空数字字符串
        } else {
            num += c; // 否则将当前字符加入数字字符串
        }
    }
    if (!num.empty()) { // 如果数字字符串不为空
        tasks.push_back(stoi(num)); // 将其转换为整数并加入任务向量
    }
    int waitTime;
    cin >> waitTime; // 输入等待时间
    unordered_map<int, int> count; // 定义哈希表，用于统计每个任务出现的次数
    for (int t : tasks) {
        count[t]++; // 统计任务出现次数
    }
    vector<vector<int>> taskList; // 定义任务列表，每个任务用一个向量表示，第一个元素为剩余次数，第二个元素为等待时间
    for (auto& p : count) { // 遍历哈希表
        taskList.push_back({p.second, 0}); // 将每个任务的出现次数加入任务列表
    }
    sort(taskList.begin(), taskList.end(), [](const vector<int>& a, const vector<int>& b) { // 按照任务出现次数从大到小排序
        return b[0] < a[0];
    });
    int total = tasks.size(); // 总任务数
    int time = 0; // 当前时间
    while (total > 0) { // 当还有任务未完成时
        time++; // 时间加一
        bool flag = true; // 标记是否已经有任务开始执行
        for (auto& task : taskList) { // 遍历任务列表
            if (flag && task[0] > 0 && task[1] == 0) { // 如果当前任务未执行且等待时间为零且还未有任务开始执行
                flag = false; // 将标记设为false，表示已经有任务开始执行
                task[0]--; // 当前任务剩余次数减一
                total--; // 总任务数减一
                task[1] = waitTime; // 将当前任务的等待时间设为输入的等待时间
            } else {
                if (task[1] > 0) { // 如果当前任务正在等待
                    task[1]--; // 等待时间减一
                }
            }
        }
    }
    cout << time << endl; // 输出完成所有任务所需的最短时间
    return 0;
}