When solving a problem, I always choose the best option at the moment, rather than consider the whole. Therefore, the greedy algorithm must ensure that the best currently selected must be the best overall.

The sample

Distribution of biscuits

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child. For each child, there is an appetite gi, which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie j has a size Sj. If sj >= gi, we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number. Given the input [1,2], [1,2,3], then the output is 2. Analysis of the following

  • To satisfy as many children as possible, the smallest cookie should be given to the person with the smallest appetite, so that the child with the largest appetite will not be left behind, and the child with the largest appetite will not be able to satisfy the small cookie. This choice also happens to be the best choice globally
public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i=0;
        int j=0;
        int num=0;
        while(i<g.length && j<s.length){
            if(s[j]>=g[i]){
                num++;
                i++;
                j++;
            }else{ j++; }}return num;
    }
Copy the code

Task scheduler

Given a list of tasks that the CPU needs to perform, represented by a character array. It contains 26 different kinds of tasks represented by capital A – Z letters. Tasks can be executed in any order, and each task can be completed in one unit of time. The CPU can perform a task at any given unit of time or be on standby.

However, there must be a cooldown of length N between two tasks of the same kind, so that there are at least n consecutive units of time in which the CPU is performing different tasks or is on standby.

You need to calculate the minimum time required to complete all the tasks. If the input tasks = [‘ A ‘, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’], n = 2 output of 8, execution order: A – > B – > (standby) – A – > B > – > (standby) – > A – > B. Analysis of the following

  • To keep the overall time to a minimum, the cooldown time must be minimal, so try to keep the execution interval between two identical tasks as long as possible n. In other wordsGreedily choose to perform n different tasksSo that the CPU can be fully utilized
  • Choose first mission, have to consider how to make the current overall is optimal choice, to choose A task A, when there is A task B it on the number of tasks than selecting A number of jobs, which means less between B an opportunity to perform A, which is added to the cooling of risk, so every choice has the maximum number of tasks to perform
public int leastInterval(char[] tasks, int n) { 
        int[] taskArr=new int[26];
        for(char c:tasks){
            taskArr[c-'A'] + +; } int maxLength=n; int interval=0;while(havaTask (taskArr)) {/ / to carry out the tasks of the maximum number of tasks in the int top = getTopTaskNotExecute (taskArr, Collections. EmptyList ()); interval++; List<Integer> list = new ArrayList<>(); list.add(top);for(int i=0; i<maxLength; Integer nextTop = getTopTaskNotExecute(taskArr, list);if (nextTop==-1){
                    maxLength=list.size()-1;
                    break;
                }
                interval++;
                list.add(nextTop);
            }
            if (list.size()-1!=n && havaTask(taskArr)){
                interval+=n-list.size()+1;
            }
        }
        return interval;
    }
    
    public boolean havaTask(int[] tasks){
        for(int i=0; i<tasks.length; i++){if(tasks[i]>0){
                return true; }}return false;
    }
    
    public Integer getTopTaskNotExecute(int[] tasks,List<Integer> executeTasks){
        int maxTaskNums=0;
        int maxNumsTaskIndex=-1;
        for(int i=0; i<tasks.length; i++){if(!executeTasks.contains(i) && tasks[i]>maxTaskNums){
                maxTaskNums=tasks[i];
                maxNumsTaskIndex=i;
            }
        }
        if(maxNumsTaskIndex! =-1){ tasks[maxNumsTaskIndex]--; }returnmaxNumsTaskIndex; }}Copy the code

Of course, if you just solve the problem, you can directly calculate the result

Or using greedy strategies as a logical consideration

  • Assume that there is only one task with the maximum number of k tasks, and at least k-1 intervals are required, then the interval consumption time is N *(k-1), and the execution time of k tasks is K, and the total time is at least N *(k-1)+ K
  • Assuming that there are more than one m tasks with the same maximum number of tasks, when the maximum number of tasks is one, there are still m-1 tasks left, and their number must be 1 and different, so the total time is N *(k-1)+k+(m-1)=(n+1)*(k-1)+ M
  • The above assumptions are only based on the maximum amount of a single task, without considering the number of independent tasks. How many tasks must be executed for at least a certain amount of time, and finally take the maximum
public int leastInterval(char[] tasks, int n) { 
int[] taskArr=new int[26];
for(char c:tasks){
    taskArr[c-'A'] + +; } Arrays.sort(taskArr); int m=0;for(int i=25; i>-1; i--){if(taskArr[i]==taskArr[25]){
        m++;
    }else{
        break; }}return Math.max(tasks.length,(taskArr[25]-1)*(n+1)+m);
}
Copy the code

The appendix

Greedy algorithm thinking