Minimum cost to process m tasks where switching costs | Java program to find out minimum cost to process m tasks ; Function to find out the farthest position where one of the currently ongoing tasks will rehappen . ; Iterate form last to current position and find where the task will happen next . ; Find out maximum of all these positions and it is the farthest position . ; Function to find out minimum cost to process all the tasks ; freqarr [ i ] [ j ] denotes the frequency of type j task after position i like in array { 1 , 2 , 1 , 3 , 2 , 1 } frequency of type 1 task after position 0 is 2. So , for this array freqarr [ 0 ] [ 1 ] = 2. Here , i can range in between 0 to m - 1 and j can range in between 0 to m ( though there is not any type 0 task ) . ; Fill up the freqarr vector from last to first . After m - 1 th position frequency of all type of tasks will be 0. Then at m - 2 th position only frequency of arr [ m - 1 ] type task will be increased by 1. Again , in m - 3 th position only frequency of type arr [ m - 2 ] task will be increased by 1 and so on . ; isRunning [ i ] denotes whether type i task is currently running in one of the cores . At the beginning no tasks are running so all values are false . ; cost denotes total cost to assign tasks ; truecount denotes number of occupied cores ; Iterate through each task and find the total cost . ; ele denotes type of task . ; Case 1 : if same type of task is currently running cost for this is 0. ; Case 2 : same type of task is not currently running . ; Subcase 1 : if there is at least one free core then assign this task to that core at a cost of 1 unit . ; Subcase 2 : No core is free ; Set minimum frequency to a big number ; Set index of minimum frequency task to 0. ; Find the minimum frequency task type ( miniind ) and frequency ( mini ) . ; If minimum frequency is zero then just stop the task and start the present task in that core . Cost for this is 1 unit . ; If minimum frequency is nonzero then find the farthest position where one of the ongoing task will rehappen . Stop that task and start present task in that core . ; Find out the farthest position using find function ; Return total cost ; Driver code ; Test case 1 ; Test case 2 ; Test case 3
import java . util . * ; class GFG { static int find ( int [ ] arr , int pos , int m , boolean [ ] isRunning ) { int [ ] d = new int [ m + 1 ] ; for ( int i = m - 1 ; i > pos ; i -- ) { if ( isRunning [ arr [ i ] ] ) d [ arr [ i ] ] = i ; } int maxipos = 0 ; for ( int ele : d ) maxipos = Math . max ( ele , maxipos ) ; return maxipos ; } static int mincost ( int n , int m , int [ ] arr ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] freqarr = new Vector [ m ] ; for ( int i = 0 ; i < freqarr . length ; i ++ ) freqarr [ i ] = new Vector < Integer > ( ) ; int [ ] newvec = new int [ m + 1 ] ; for ( int i = 0 ; i < m + 1 ; i ++ ) freqarr [ m - 1 ] . add ( newvec [ i ] ) ; for ( int i = m - 2 ; i > 0 ; i -- ) { Vector < Integer > nv = new Vector < > ( ) ; nv = freqarr [ i + 1 ] ; nv . insertElementAt ( arr [ i + 1 ] + 1 , arr [ i + 1 ] ) ; freqarr [ i ] = nv ; } boolean [ ] isRunning = new boolean [ m + 1 ] ; int cost = 0 ; int truecount = 0 ; for ( int i = 0 ; i < m ; i ++ ) { int ele = arr [ i ] ; if ( isRunning [ ele ] == true ) continue ; else { if ( truecount < n ) { cost += 1 ; truecount += 1 ; isRunning [ ele ] = true ; } else { int mini = 100000 ; int miniind = 0 ; for ( int j = 0 ; j <= m ; j ++ ) { if ( isRunning [ j ] && mini > freqarr [ i ] . get ( j ) ) { mini = freqarr [ i ] . get ( j ) ; miniind = j ; } } if ( mini == 0 ) { isRunning [ miniind ] = false ; isRunning [ ele ] = true ; cost += 1 ; } else { int farpos = find ( arr , i , m , isRunning ) ; isRunning [ arr [ farpos ] ] = false ; isRunning [ ele ] = true ; cost += 1 ; } } } } return cost ; } public static void main ( String [ ] args ) { int n1 = 3 ; int m1 = 6 ; int [ ] arr1 = { 1 , 2 , 1 , 3 , 4 , 1 } ; System . out . print ( mincost ( n1 , m1 , arr1 ) + "NEW_LINE"); int n2 = 2 ; int m2 = 6 ; int [ ] arr2 = { 1 , 2 , 1 , 3 , 2 , 1 } ; System . out . print ( mincost ( n2 , m2 , arr2 ) + "NEW_LINE"); int n3 = 3 ; int m3 = 31 ; int [ ] arr3 = { 7 , 11 , 17 , 10 , 7 , 10 , 2 , 9 , 2 , 18 , 8 , 10 , 20 , 10 , 3 , 20 , 17 , 17 , 17 , 1 , 15 , 10 , 8 , 3 , 3 , 18 , 13 , 2 , 10 , 10 , 11 } ; System . out . print ( mincost ( n3 , m3 - 8 , arr3 ) + "NEW_LINE"); } }