Minimize cost to reach end of an N | Java program for the above approach ; Function to calculate the minimum cost required to reach the end of Line ; Checks if possible to reach end or not ; Stores the stations and respective rate of fuel ; Stores the station index and cost of fuel and litres of petrol which is being fueled ; Iterate through the entire line ; Check if there is a station at current index ; Remove all the stations where fuel cannot be pumped ; If there is no station left to fill fuel in tank , it is not possible to reach end ; Stores the best station visited so far ; Pump fuel from the best station ; Update the count of litres taken from that station ; Update the bunk in queue ; Print the cost ; Driver Code ; Given value of N , K & M ; Given arrays ; Function call to calculate minimum cost to reach end of the line
import java . util . * ; public class Main { static void minCost ( int N , int K , int M , int [ ] a , int [ ] b ) { boolean flag = true ; HashMap < Integer , Integer > map = new HashMap < > ( ) ; for ( int i = 0 ; i < M ; i ++ ) { map . put ( a [ i ] , b [ i ] ) ; if ( i == M - 1 && K < N - a [ i ] ) { flag = false ; break ; } else if ( i < M - 1 && K < a [ i + 1 ] - a [ i ] ) { flag = false ; break ; } } if ( ! flag ) { System . out . println ( " - 1" ) ; return ; } PriorityQueue < int [ ] > pq = new PriorityQueue < > ( ( c , d ) -> c [ 1 ] - d [ 1 ] ) ; int cost = 0 ; flag = false ; for ( int i = 0 ; i < N ; i ++ ) { if ( map . containsKey ( i ) ) pq . add ( new int [ ] { i , map . get ( i ) , 0 } ) ; while ( pq . size ( ) > 0 && pq . peek ( ) [ 2 ] == K ) pq . poll ( ) ; if ( pq . size ( ) == 0 ) { flag = true ; break ; } int best_bunk [ ] = pq . poll ( ) ; cost += best_bunk [ 1 ] ; best_bunk [ 2 ] ++ ; pq . add ( best_bunk ) ; } if ( flag ) { System . out . println ( " - 1" ) ; return ; } System . out . println ( cost ) ; } public static void main ( String args [ ] ) { int N = 10 , K = 3 , M = 4 ; int a [ ] = { 0 , 1 , 4 , 6 } ; int b [ ] = { 5 , 2 , 2 , 4 } ; minCost ( N , K , M , a , b ) ; } }