Find time taken to execute the tasks in A based on the order of execution in B
Given two queues A and B, each of size N, the task is to find the minimum time taken to execute the tasks in A based on the order of execution in B where:
- If the task found at the front of queue B is at the front of queue A, then pop this task and execute it.
- If the task found at the front of queue B is not found at the front of queue A, then pop the current task from queue A and push it at the end.
- Push and Pop operation in a queue costs one unit of time and the execution of a task is done in constant time.
Example
Input: A = { 3, 2, 1 }, B = { 1, 3, 2 }
Output: 7
Explanation:
For A = 3 and B = 1 => Since the front of queue A does not match with the front of queue B. Pop and Push 3 at the back of Queue. Then, A becomes { 2, 1, 3 } and time consumed = 2 ( 1 unit of time for each push and pop operation)
For A = 2 and B = 1 => Since the front of queue A does not match with the front of queue B. Pop and Push 2 at the back of Queue. Then, A becomes { 1, 3, 2 } and time = 2 + 2 = 4
For A = 1 and B = 1 => Since the front of queue, A equals to front of queue B. Pop 1 from both the queue and execute it, Then A becomes { 3, 2 } and B becomes { 3, 2 } and time = 4 + 1 = 5
For A = 3 and B = 3 => Since the front of queue, A equals to front of queue B. Pop 3 from both the queue and execute it, Then A becomes { 2 } and B becomes { 2 } and time = 5 + 1 = 6
For A = 2 and B = 2 => Since the front of the queue, A equals to front of queue B. Pop 2 from both the queue and execute it. All the tasks are executed. time = 6 + 1 = 7
Therefore the total time is 7.Input: A = { 3, 2, 1, 4 }, B = { 4, 1, 3, 2 }
Output: 14
Approach:
For each task in queue A:
- If the front task of queue A is the same as the front task of queue B. Pop the task from both the queues and execute it. Increment the total time by one unit.
- If the front task of queue A is not the same as the front task of queue B. Pop the task from queue A and push it at the back of queue A and increment the total time by two units. (1 for pop operation and 1 for push operation)
- Repeat the above steps till all the task in queue A is executed.
Below is the implementation of the above approach:
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> |
14
Time Complexity: O(N2), where N is the number of tasks.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Contact Us