C++ 在不改变顺序的情况下完成所有任务所需的最短时间

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

我们可以使用映射数据结构来解决这个问题。我们可以跟踪每个任务的最后执行时间，并且如果时间间隔小于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]，并将结果加 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)，因为我们不使用任何动态空间。