完成所有任务所需的最短时间（不改变任务顺序）

---

在这个问题中，我们需要根据给定的条件找到完成所有任务所需的总时间。

我们可以使用映射数据结构来解决这个问题。我们可以跟踪每个任务最后执行的时间，如果时间间隔小于K，我们可以相应地增加时间单位。

问题陈述 – 我们得到一个包含长度为N的字母字符的字符串task。每个字符代表一个任务，我们需要一个时间单位来执行任务。此外，条件是每个任务都应该以K个单位的时间间隔执行。这里，K是输入中给出的正整数。打印按给定顺序完成所有任务所需的总时间单位。

示例

输入– str = "BADBBC", K = 3

输出– 10

解释– 我们可以按给定顺序执行任务。

B -> A -> D -> _ -> B -> _ -> _ -> _ -> B -> C

这里，程序员可以观察到“_”代表单个时间单位，以跳过在3个时间间隔内执行相同任务。

输入– str = “RSTUV”, K = 2

输出– 5

解释我们可以按给定顺序执行任务。

R -> S -> T -> U -> V

输入– str = ‘HHHH’, K = 2

输出– 10

解释– 我们可以按给定顺序执行任务。

H -> _ -> _ -> H -> _ -> _ -> H -> _ -> _ -> H

方法一

在这种方法中，我们将每个任务最后执行的时间存储在哈希映射中。如果任何任务重复，并且当前时间和上次执行任务之间的时间间隔小于K，我们需要添加额外的时间单位以使时间间隔等于K。

算法

• 定义名为“time”的无序映射来跟踪特定任务最后执行的时间单位。

• 将“ans”初始化为零以存储总时间单位。

• 遍历任务字符串。

• 如果当前字符存在于映射中，则表示已执行相同的任务。

• 从映射中查找上次执行当前任务的时间单位。如果“ans”（当前时间单位）和time[ch]之间的差小于K，我们需要按照下面给出的步骤4.2向ans添加一些时间单位。

• 从K中减去ans - time[ch]，然后向K加1。之后，将结果值添加到ans中。

• 将“ans”的值存储在字符“ch”的映射中。

• 将“ans”的值增加1。

• 返回“ans”的值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the minimum time required to complete the tasks according to the given conditions
int minimumTime(string tasks, int K){
    // Keeps track of the last time instant of each task
    unordered_map<char, int> time;
    // to keep track of the current time
    int ans = 0;
    // Traverse the given string
    for (char ch : tasks){
        // Check if the same task exists in the map
        if (time.find(ch) != time.end()){
            // If the same task exists and its last time instant is less than K, then update the time of the current task.
            if (ans - time[ch] <= K){
                ans += K - (ans - time[ch]) + 1;
            }
        }
        // Update the last time instant of the current task
        time[ch] = ans;
        // Increase the current time by 1
        ans++;
    }
    // return the minimum time required
    return ans;
}

int main(){
    string str = "BADBBC";
    int K = 3;
    cout << "The minimum time required to complete all tasks is " << minimumTime(str, K);
    return 0;
}

输出

The minimum time required to complete all tasks is 10

时间复杂度 – O(N)，因为我们迭代字符串。

空间复杂度 – O(1)，因为我们不使用任何动态空间。