Dsa
Greedy
Easy
The Road Trip Refuel
You are driving an electric truck that needs exactly K units of energy to reach its destination. You pass through N charging zones. Each zone i offers up to L[i] units of energy at a price of P[i] per unit. You can buy any amount of energy from a zone, including fractional amounts, as long as it does not exceed L[i]. Find the minimum cost to obtain exactly K units of energy.
Input Format:
The first line contains two integers: N (number of zones) and K (energy needed). The next N lines each contain P[i] (price) and L[i] (limit).
Output Format:
A single integer representing the minimum cost (rounded down to the nearest integer).
Example:
Input:
2 10
5 6
2 8
Output:
34
Explanation: Buy 8 units from zone 2 (cost 16) and 2 units from zone 1 (cost 10). Total 26? Wait, the example calculation is: 8*2 = 16, 2*5 = 10. Total 26.
Key concepts
greedyresource-allocationsorting
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now