The Greedy Technique is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. It is used for optimization problems where local choices lead to a globally optimal solution.
class Solution {
public int findMaxProfit(int[] tasks) {
Arrays.sort(tasks); // Sort tasks based on a specific criterion
int profit = 0;
for (int task : tasks) {
if (isFeasible(task)) { // Check if the task can be included
profit += task;
}
}
return profit;
}
private boolean isFeasible(int task) {
// Implement feasibility check logic
return true;
}
}O(N log N), where N is the size of the input.O(N), for iterating through the sorted input.O(N log N).Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation:
- Use coins [5, 5, 1] to make up the amount 11 with the minimum number of coins.