Dada una string S que consta de N caracteres (que representan las tareas a realizar) y un número entero positivo K , la tarea es encontrar el tiempo mínimo requerido para completar todas las tareas dadas en el orden dado, de modo que cada tarea tome una unidad de tiempo y cada tarea del mismo tipo debe realizarse en un intervalo de K unidades .
Ejemplos:
Entrada: S = “ABACCA”, K = 2
Salida: 9
Explicación:
A continuación se muestra el orden de la tarea que se debe completar:
A → B → _ → A → C → _ → _ → C → A.
Por lo tanto, el total el tiempo requerido es de 9 unidades.Entrada: S = “AAAA”, K = 3
Salida: 13
Enfoque: Hashing puede resolver el problema dado al realizar un seguimiento del último instante de cada tarea y encontrar el tiempo mínimo general en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice un hashmap , digamos M , para realizar un seguimiento del último instante de tiempo de cada tarea.
- Inicialice una variable, digamos ans como 0 , para almacenar el tiempo mínimo resultante.
- Atraviese la string S dada y realice los siguientes pasos:
- Si el carácter S[i] está presente en M , almacene el último instante de S[i] en una variable, digamos t .
- Si el valor de (ans – t) es como máximo K , entonces agregue el valor de K – (ans – t) + 1 a la variable ans .
- Actualice el último instante de tiempo del carácter S[i] en M a ans e incremente el valor de ans en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// 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.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the minimum
// time required to complete
// tasks without changing their order
static void findMinimumTime(
String tasks, int K)
{
// Keeps track of the last
// time instant of each task
Map<Character, Integer> map
= new HashMap<>();
// Stores the required result
int curr_time = 0;
// Traverse the given string
for (char c : tasks.toCharArray()) {
// Check last time instant of
// task, if it exists before
if (map.containsKey(c)) {
// Increment the time
// if task is within
// the K units of time
if (curr_time
- map.get(c)
<= K) {
curr_time += K
- (curr_time
- map.get(c))
+ 1;
}
}
// Update the time of the
// current task in the map
map.put(c, curr_time);
// Increment the time by 1
curr_time++;
}
// Print the result
System.out.println(curr_time);
}
// Driver Code
public static void main(String[] args)
{
String S = "ABACCA";
int K = 2;
findMinimumTime(S, K);
}
}
Python3
# Python 3 implementation of
# the above approach
# Function to find the minimum
# time required to complete
# tasks without changing their order
def findMinimumTime(tasks, K):
# Keeps track of the last
# time instant of each task
map = {}
# Stores the required result
curr_time = 0
# Traverse the given string
for c in tasks:
# Check last time instant of
# task, if it exists before
if (c in map):
# 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 += 1
# Print the result
print(curr_time)
# Driver Code
if __name__ == "__main__":
S = "ABACCA"
K = 2
findMinimumTime(S, K)
# This code is contributed by ukasp.
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum
// time required to complete
// tasks without changing their order
static void findMinimumTime(String tasks, int K)
{
// Keeps track of the last
// time instant of each task
Dictionary<char,
int> map = new Dictionary<char,
int>();
// Stores the required result
int curr_time = 0;
// Traverse the given string
foreach (char c in tasks.ToCharArray())
{
// Check last time instant of
// task, if it exists before
if (map.ContainsKey(c))
{
// 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
if (!map.ContainsKey(c))
map.Add(c, curr_time);
else
map = curr_time;
// Increment the time by 1
curr_time++;
}
// Print the result
Console.WriteLine(curr_time);
}
// Driver Code
public static void Main(String[] args)
{
String S = "ABACCA";
int K = 2;
findMinimumTime(S, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to find the minimum
// time required to complete
// tasks without changing their order
function findMinimumTime(tasks, K)
{
// Keeps track of the last
// time instant of each task
var map = new Map();
// Stores the required result
var curr_time = 0;
// Traverse the given string
tasks.split('').forEach(c => {
// Check last time instant of
// task, if it exists before
if (map.has(c)) {
// Increment the time
// if task is within
// the K units of time
if (curr_time - map.get(c) <= K) {
curr_time += K - (curr_time - map.get(c)) + 1;
}
}
// Update the time of the
// current task in the map
map.set(c, curr_time);
// Increment the time by 1
curr_time++;
});
// Print the result
document.write( curr_time);
}
// Driver Code
var S = "ABACCA";
var K = 2;
findMinimumTime(S, K);
// This code is contributed by rutvik_56.
</script>
Producción:
9
Complejidad temporal: O(N)
Espacio auxiliar: O(256)