Dadas dos colas A y B , cada una de tamaño N , la tarea es encontrar el tiempo mínimo necesario para ejecutar las tareas en A en función del orden de ejecución en B , donde:
- Si la tarea que se encuentra al frente de la cola B está al frente de la cola A , entonces extraiga esta tarea y ejecútela.
- Si la tarea que se encuentra al principio de la cola B no se encuentra al principio de la cola A , extraiga la tarea actual de la cola A y empújela al final.
- La operación Push and Pop en una cola cuesta una unidad de tiempo y la ejecución de una tarea se realiza en tiempo constante.
Ejemplo
Entrada: A = { 3, 2, 1 }, B = { 1, 3, 2 }
Salida: 7
Explicación:
Para A = 3 y B = 1 => Dado que el frente de la cola A no coincide con el frente de la cola B. Pop and Push 3 al final de la cola. Entonces, A se convierte en { 2, 1, 3 } y el tiempo consumido = 2 (1 unidad de tiempo para cada operación de empujar y abrir)
Para A = 2 y B = 1 => Dado que el frente de la cola A no coincide con el frente de la cola B. Pop y Push 2 al final de la cola. Entonces, A se convierte en { 1, 3, 2 } y el tiempo = 2 + 2 = 4
Para A = 1 y B = 1 => Dado que el frente de la cola, A es igual al frente de la cola B. Extraiga 1 de la cola y ejecutarlo, entonces A se convierte en { 3, 2 } y B se convierte en { 3, 2 } y el tiempo = 4 + 1 = 5
Para A = 3 y B = 3 => Dado que el frente de la cola, A es igual al frente de la cola B. Extraiga 3 de la cola y ejecútelo, luego A se convierte en { 2 } y B se convierte en { 2 } y el tiempo = 5 + 1 = 6
Para A = 2 y B = 2 => Desde el frente de la cola, A es igual al frente de la cola B. Extraiga 2 de ambas colas y ejecútelo. Todas las tareas se ejecutan. tiempo = 6 + 1 = 7
Por lo tanto, el tiempo total es 7.Entrada: A = { 3, 2, 1, 4 }, B = { 4, 1, 3, 2 }
Salida: 14
Enfoque:
Para cada tarea en la cola A :
- Si la tarea principal de la cola A es la misma que la tarea principal de la cola B. Extraiga la tarea de ambas colas y ejecútela. Incrementa el tiempo total en una unidad.
- Si la tarea principal de la cola A no es la misma que la tarea principal de la cola B. Extraiga la tarea de la cola A y empújela al final de la cola A e incremente el tiempo total en dos unidades. (1 para operación pop y 1 para operación push)
- Repita los pasos anteriores hasta que se ejecute toda la tarea en la cola A.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the total
// time taken to execute the task
// in given order
#include "bits/stdc++.h"
using namespace std;
// Function to calculate the
// total time taken to execute
// the given task in original order
int run_tasks(queue<int>& A,
queue<int>& B)
{
// To find the total time
// taken for executing
// the task
int total_time = 0;
// While A is not empty
while (!A.empty()) {
// Store the front element of queue A and B
int x = A.front();
int y = B.front();
// If the front element of the queue A
// is equal to the front element of queue B
// then pop the element from both
// the queues and execute the task
// Increment total_time by 1
if (x == y) {
A.pop();
B.pop();
total_time++;
}
// If front element of queue A is not equal
// to front element of queue B then
// pop the element from queue A &
// push it at the back of queue A
// Increment the total_time by 2
//(1 for push operation and
// 1 for pop operation)
else {
A.pop();
A.push(x);
total_time += 2;
}
}
// Return the total time taken
return total_time;
}
// Driver Code
int main()
{
// Given task to be executed
queue<int> A;
A.push(3);
A.push(2);
A.push(1);
A.push(4);
// Order in which task need to be
// executed
queue<int> B;
B.push(4);
B.push(1);
B.push(3);
B.push(2);
// Function the returns the total
// time taken to execute all the task
cout << run_tasks(A, B);
return 0;
}
Java
// Java program to find the total
// time taken to execute the task
// in given order
import java.util.*;
class GFG
{
// Function to calculate the
// total time taken to execute
// the given task in original order
static int run_tasks(Queue<Integer> A,
Queue<Integer> B)
{
// To find the total time
// taken for executing
// the task
int total_time = 0;
// While A is not empty
while (!A.isEmpty())
{
// Store the front element of queue A and B
int x = A.peek();
int y = B.peek();
// If the front element of the queue A
// is equal to the front element of queue B
// then pop the element from both
// the queues and execute the task
// Increment total_time by 1
if (x == y)
{
A.remove();
B.remove();
total_time++;
}
// If front element of queue A is not equal
// to front element of queue B then
// pop the element from queue A &
// push it at the back of queue A
// Increment the total_time by 2
//(1 for push operation and
// 1 for pop operation)
else
{
A.remove();
A.add(x);
total_time += 2;
}
}
// Return the total time taken
return total_time;
}
// Driver Code
public static void main(String[] args)
{
// Given task to be executed
Queue<Integer> A = new LinkedList<Integer>();
A.add(3);
A.add(2);
A.add(1);
A.add(4);
// Order in which task need to be
// executed
Queue<Integer> B = new LinkedList<Integer>();
B.add(4);
B.add(1);
B.add(3);
B.add(2);
// Function the returns the total
// time taken to execute all the task
System.out.print(run_tasks(A, B));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find the total # time taken to execute the task # in given order from collections import deque # Function to calculate the # total time taken to execute # the given task in original order def run_tasks(A, B): # To find the total time # taken for executing # the task total_time = 0 # While A is not empty while (len(A) > 0): # Store the front element of queue A and B x = A.popleft() y = B.popleft() # If the front element of the queue A # is equal to the front element of queue B # then pop the element from both # the queues and execute the task # Increment total_time by 1 if (x == y): total_time += 1 # If front element of queue A is not equal # to front element of queue B then # pop the element from queue A & # append it at the back of queue A # Increment the total_time by 2 #(1 for append operation and # 1 for pop operation) else: B.appendleft(y) A.append(x) total_time += 2 # Return the total time taken return total_time # Driver Code if __name__ == '__main__': # Given task to be executed A = deque() A.append(3) A.append(2) A.append(1) A.append(4) # Order in which task need to be # executed B = deque() B.append(4) B.append(1) B.append(3) B.append(2) # Function the returns the total # time taken to execute all the task print(run_tasks(A, B)) # This code is contributed by mohit kumar 29
C#
// C# program to find the total
// time taken to execute the task
// in given order
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate the
// total time taken to execute
// the given task in original order
static int run_tasks(Queue<int> A,
Queue<int> B)
{
// To find the total time
// taken for executing
// the task
int total_time = 0;
// While A is not empty
while (A.Count != 0)
{
// Store the front element of queue A and B
int x = A.Peek();
int y = B.Peek();
// If the front element of the queue A
// is equal to the front element of queue B
// then pop the element from both
// the queues and execute the task
// Increment total_time by 1
if (x == y)
{
A.Dequeue();
B.Dequeue();
total_time++;
}
// If front element of queue A is not equal
// to front element of queue B then
// pop the element from queue A &
// push it at the back of queue A
// Increment the total_time by 2
//(1 for push operation and
// 1 for pop operation)
else
{
A.Dequeue();
A.Enqueue(x);
total_time += 2;
}
}
// Return the total time taken
return total_time;
}
// Driver Code
public static void Main(String[] args)
{
// Given task to be executed
Queue<int> A = new Queue<int>();
A.Enqueue(3);
A.Enqueue(2);
A.Enqueue(1);
A.Enqueue(4);
// Order in which task need to be
// executed
Queue<int> B = new Queue<int>();
B.Enqueue(4);
B.Enqueue(1);
B.Enqueue(3);
B.Enqueue(2);
// Function the returns the total
// time taken to execute all the task
Console.Write(run_tasks(A, B));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find the total
// time taken to execute the task
// in given order
// Function to calculate the
// total time taken to execute
// the given task in original order
function run_tasks(A, B)
{
// To find the total time
// taken for executing
// the task
let total_time = 0;
// While A is not empty
while (A.length != 0)
{
// Store the front element of
// queue A and B
let x = A[0];
let y = B[0];
// If the front element of the queue A
// is equal to the front element of queue B
// then pop the element from both
// the queues and execute the task
// Increment total_time by 1
if (x == y)
{
A.shift();
B.shift();
total_time++;
}
// If front element of queue A is not equal
// to front element of queue B then
// pop the element from queue A &
// push it at the back of queue A
// Increment the total_time by 2
//(1 for push operation and
// 1 for pop operation)
else
{
A.shift();
A.push(x);
total_time += 2;
}
}
// Return the total time taken
return total_time;
}
// Driver code
// Given task to be executed
let A = [ 3, 2, 1, 4 ];
// Order in which task need to be
// executed
let B = [ 4, 1, 3, 2 ];
// Function the returns the total
// time taken to execute all the task
document.write(run_tasks(A, B));
// This code is contributed by patel2127
</script>
Producción:
14
Complejidad Temporal: O(N 2 ), donde N es el número de tareas.
Publicación traducida automáticamente
Artículo escrito por Gaurang Bansal 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA