时间戳

首页 > 解决方案 > 在不改变顺序的情况下完成所有任务所需的最短时间

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

问题描述

最短时间要求问题：

给定一个由 N 个字符（表示要执行的任务）和一个正整数 K 组成的字符串 S，任务是找到按给定顺序完成所有给定任务所需的最短时间，使得每个任务花费一个单位时间，并且每个相同类型的任务必须以 K 个单位的间隔执行。

链接到这里的问题 - >链接

我不明白以下部分，特别是curr_time - map以下代码中的内容。确实了解是什么curr_time，但curr_time - map我不明白。

// C++ implementation of
// the above approach
#include <bits/stdc++.h>

using namespace std;

// Function to find the minimum
// time required to complete
// tasks without changing their order
void findMinimumTime(string tasks, int K)
{
    // Keeps track of the last
    // time instant of each task
    unordered_map<char, int> map;

    // Stores the required result
    int curr_time = 0;

    // Traverse the given string
    for (char c : tasks) {

        // Check last time instant of
        // task, if it exists before
        if (map.find(c) != map.end()) {

            // Increment the time
            // if task is within
            // the K units of time
            if (curr_time - map <= K) {

                curr_time += K - (curr_time - map) + 1;
            }
        }

        // Update the time of the
        // current task in the map
        map = curr_time;

        // Increment the time by 1
        curr_time++;
    }

    // Print the result
    cout << curr_time;
}

// Driver Code
int main()
{
    string S = "ABACCA";
    int K = 2;
    findMinimumTime(S, K);

    return 0;
}

// This code is contributed by Kingash.

标签： c++hashmap

解决方案

似乎他们不检查其他人提交的内容是否正确。在这段代码中，无论它有什么map，它都应该有map[c]：

        if (curr_time - map[c] <= K) {

            curr_time += K - (curr_time - map[c]) + 1;
        }

    ...

    // Update the time of the
    // current task in the map
    map[c] = curr_time;

推荐阅读