完成所有任務所需的最短時間（不改變任務順序）

---

在這個問題中，我們需要根據給定的條件找到完成所有任務所需的總時間。

我們可以使用對映資料結構來解決這個問題。我們可以跟蹤每個任務最後執行的時間，如果時間間隔小於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)，因為我們不使用任何動態空間。