Greedy algorithm

What is a greedy algorithm?

Greedy algorithm is a relatively simple algorithm, its core idea is to ensure that every operation is locally optimal, so that the final result is optimal. Let’s look at a simple example to learn more about greedy algorithms:

Minimum paper money payment problem

Problem Description:

We go to the store and we have 100, 50, 20, 10, 5, 2, 1 bills in sufficient quantities. We select a 788 product, how can we pay with the minimum amount of paper money when we settle the account?

Answer:

We pay each time with the largest denomination bill currently available, then subtract the corresponding amount from the total amount to be paid, and repeat the previous steps until the total amount to be paid becomes 0. The specific steps are as follows:

  1. We divide $788 by $100, the largest denomination currently available, to get 7, so we take seven $100 bills and we have to pay $88.

  2. We divide $88 by $50, the largest available denomination, to get 1, so we use a $50 bill and pay $38.

  3. We divide $38 by $20, the largest available denomination, to get 1, so we use a $20 bill and pay $18.

  4. We divide $18 by $10, the largest denomination currently available, to get 1, so we use a $10 bill and pay $8.

  5. We divide $8 by $5, the largest available denomination, to get $1, so we use a $5 bill and have to pay $3.

  6. We divide $3 by $2, the largest currently available denomination, to get $1, so we use a $2 bill and we have to pay $1.

  7. We divide $1 by the largest available $1 denomination to get $1, so we use a $1 bill and pay $0.

So far, we have come to a conclusion: for a 788 yuan dress, the least amount of paper money used is 13 bills: 7 100 yuan, 1 50 yuan, 1 20 yuan, 1 10 yuan, 1 5 yuan, 1 2 yuan, and 1 1 yuan.

The above problem is the most typical greedy algorithm, we constantly choose the locally optimal one among the remaining choices, and finally get the global optimal result.

Js code implementation:

function payMoney(money) {
    const moneyArr = [100.50.20.10.5.2.1];
    let _money = money;
    let total = 0; // The final amount of banknotes to use
    for(let i = 0; i < moneyArr.length; i++) {
        // The current denomination of the note
        const nowMoney = moneyArr[i];
        if(_money >= nowMoney) {
            // The current total amount divided by the current maximum denomination amount, rounded down to get the current maximum number of notes, add to the total
            total += Math.floor(_money / nowMoney); _money = _money % nowMoney; }}return total;
}
Copy the code

Analyzing time complexity:

The core loop part of the code above (i.e., the denomination of each note used) is traversed seven times in constant time complexity.

So the time complexity is: O(n) = 1;

Application scenarios

Greedy algorithm can be generally applied to two scenarios:

  • Allocation problem

  • Range of problems

The minimum paper payment problem that we just solved is a typical assignment problem, and we’re going to look at a couple of assignment problems and interval problems.

Distribution problem – Deformation: cookie distribution

Description of the title (corresponding to Leecode 455)

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 I, there is an appetite value g[I], which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie J has a size S [J]. If s[j] >= g[I], 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.

Input and output examples:

The sample1: Input: g = [1.2.3], s = [1.1.2] output:2Explanation: You have three kids and two cookies,3The appetite values of each child are:1.2.3. You have three little cookies, and their sizes are1.1.2You can only let your appetite be1And appetite is2Are satisfied with their children. So you should output2. The sample2: Input: g = [1.2], s = [1.2.3] output:2Explanation: You have two kids and three cookies,2The appetites of each child are1.2. The number and size of cookies you have is enough to satisfy all children. So you should output2.
Copy the code

Their thinking

To satisfy as many children as possible, it is simple, we satisfy the child with the smallest appetite first, then the child with the second smallest appetite… , until there are no cookies or all the children are satisfied, the traversal ends. Using Example 1 as an example, let’s look at the steps:

  1. First, each child was ranked from smallest to largest in terms of appetite (in parameter group g) [1,2,3], and then biscuits were ranked from smallest to largest in terms of size (in parameter group s) [1,2]. (current g:[1,2,3], s:[1,1,2])

  2. We take the current smallest cookie (size 1) and ask the child with the current smallest appetite (appetite 1) if this cookie satisfies you. Finding yes, we give the cookie to the child (corresponding to array S and array G with the top element) and move on to the next cookie and the next child. (current g:[2,3], s:[1,2])

  3. We took out the smallest cookies (size of 1), we took out the smallest cookies (size of 1), q current appetite is the youngest child (appetite for 2), the biscuit can satisfy you, found that can not meet, we will biscuits down (as corresponding g launch the head of the array), continue to find a cookie. (current g:[2,3], s:[2])

  4. We take the current smallest cookie (size 2) and ask the child with the current smallest appetite (size 2) if this cookie satisfies you. If yes, we give the cookie to the child (corresponding to array S and array G with the top element) and move on to the next cookie and the next child. (current g:[3], s:[])

  5. We find that there are no cookies (that is, the length of S is 0), the end of traversal, output the number of children that can be satisfied at present, that is, the problem is solved.

Js code implementation

function findContentChildren(g, s) {
    / / first order
    g.sort((a,b) = > a - b);
    s.sort((a,b) = > a - b);
    
    let result = 0;
    
    while(g.length && s.length) {
        if(s[0] >= g[0]) {
            result ++;
            g.shift();
            s.shift();
        } else{ s.shift(); }}return result;
}
Copy the code

Analyzing time complexity

In the above code, the sorting is traversed mlogm times and nlogn times, respectively,

The core loop sections (where S and G derive the first element) are traversed at most m and N times.

Since the former is larger than the latter in the asymptotic sense, the total time complexity is O(Mlogm + Nlogn).

Distribution problem – remorphing: candy problem

Description of the title (corresponding to Leecode question 135)

The teacher wants to hand out candy to the children. There are N children standing in a straight line, and the teacher will score each child in advance according to their performance.

You need to help the teacher to distribute sweets to these children according to the following requirements:

Each child gets at least one candy. The child who scored higher had to get more candy than the child on either side of him. So how many candies should the teacher prepare?

Input and output examples

The sample1: Input: [1.0.2] output:5Explanation: You can give them to each of the three children2,1,2Candy. The sample2: Input: [1.2.2] output:4Explanation: You can give them to each of the three children1,2,1Candy. The third child only gets1Candy, which meets both of the above conditions.Copy the code

Their thinking

Since each child gets at least one candy, we give one candy to each child first. And since the child with a higher rating has to get more candy than the child on either side of him or her, we go from left to right and set the number of candy for the child with a higher rating than the child on his or her left side to +1. After this round, we were satisfied: the child who scored higher had more candy than the child next to him. We then iterate from right to left again, and set the number of sweets for the child rated higher than his right to the maximum of the current number and the number of sweets he should have (the number of sweets for the child on his right +1). After this round of iteration, we are satisfied that the child with higher score has more candy than the child with adjacent position on both sides of him, namely, the problem is solved. Using Example 1 as an example, let’s look at the steps:

  1. Input is [1,0,2], that is, there are 3 children, corresponding to the rating of 1,0,2 respectively.

  2. We set an array result with an initial value of [1,1,1] to hold the number of candies to be given to each child (we start with one candy per child).

  3. We go from left to right (the front to the back of the array) and give more candy to the child who scores higher than the child on the left.

1.The subscript for0Children, no children left, skip. Where result is [1.1.1].2.The subscript for1Of his children, his ratings (0) there was no rating of children on the left (1) High, skip. Where result is [1.1.1].3.The subscript for2Of his children, his ratings (2) than children on the left (1) high, set the number of his candies to the number of children's candies on the left (1) +1. Where result is [1.1.2].4.At this point the subscript2We're at the end of the array, we're done iterating, and we get that the kid who scored higher has more candy than the kid who's next to him.Copy the code
  1. We iterate from right to left, giving more candy to the child who scored higher than the child on the right.
1.The subscript for2Children, no children on the right, skip. Where result is [1.1.2] (the result of the first pass).2.The subscript for1Of his children, his ratings (0) there is no rating of children on the right (2) High, skip. Where result is [1.1.2].3.The subscript for0Of his children, his ratings (1) than children on the right (0) high, set the number of his candies to the number of children's candies on the right (1) +1. Where result is [2.1.2].4.At this point the subscript2We're at the head of the array, we're at the end of the loop, and the kid who scored higher has more candy than the kid on either side of him.Copy the code

Note: In the second pass, we need to compare the number of candies of the current child with the number of candies of the child on the right. If the number of candies of the child on the right itself is not as high as the number of candies of the child on the left, we do not need to do extra processing and just skip it.

  1. The third iteration (traversing the results array) adds up the number of sweets each child gets to get the final result.

Js code implementation

var candy = function(ratings) {
    const total = ratings.length;
    // Initialize a one-bit array of children, each of which is 1, to hold the number of sweets per child
    const arr = new Array(total).fill(1);
    for(let i = 1 ; i < total; i++) {
        if(ratings[i] > ratings[i-1]) {
            arr[i] = arr[i - 1] + 1; }}for(let j = total - 1; j >= 0; j--) {
        if(ratings[j] > ratings[j+1]) {
            // Take the maximum number of candies for the current child and the number of candies for the right child +1
            arr[j] = Math.max(arr[j], arr[j + 1] + 1); }}let result = 0;
    arr.forEach((item) = > result+= item);
    return result;
};
Copy the code

Analyzing time complexity

The core loop part of the above code is executed 3n times. Respectively is:

  1. Go left to right n times

  2. Go right to left n times

  3. Iterate over the result array n times

Is the time complexity of linear time, so the time complexity is O(n) = n.

Interval problem: no overlapping interval

Topic describes

Given a set of intervals, find the minimum number of intervals to remove so that the remaining intervals do not overlap.

Note: The end of the interval can always be considered greater than its start. The boundaries of the intervals [1,2] and [2,3] “touch” each other, but do not overlap each other.

Input and output examples

The sample1: Input: [[1.2], [2.3], [3.4], [1.3] output:1Explanation: Remove [1.3], the remaining interval does not overlap. The sample2: Input: [[1.2], [1.2], [1.2] output:2Explanation: You need to remove two [1.2] so that the rest of the interval does not overlap.Copy the code

Their thinking

The description of this topic is not as intuitive as the previous questions, but the idea is relatively simple. We first order all the intervals from smallest to smallest, so that the end point of each previous interval is not less than the end point of the following interval. At this time all is the end point of the first interval of interval end the smallest one, if after an interval of starting point is greater than the end of the current interval or equivalent, so they must not overlap range, we plug it to the back of the first interval, and then compare the second and the next interval, traverse time, we can find the most how many intervals are not overlap, So the total number of intervals minus the number of non-overlapping intervals is the solution. Let’s take example 1 as an example to see the specific steps:

  1. We will range according to the finish size sorting, sorted results: [[1, 2], [2, 3], [1, 3], [3, 4]].

  2. We put the interval [1,2] into the result array (result: [[1,2]])

  3. Then interval [1,2] and interval [2,3] are compared, and it is found that the starting point 2 of interval [2,3] is equal to the end point 2 of [1,2], and interval [2,3] do not overlap. We place the interval [2,3] into the result array (result: [[1,2], [2,3]])

  4. We continue to compare interval [2,3] and interval [1,3], and find that the starting point 1 of interval [1,3] is less than the end point 2 of interval [2,3], which overlapped with interval 3 and skipped interval 3

  5. The comparison between interval [2,3] and interval [3,4] continues, and it is found that the starting point 3 of interval [3,4] is equal to the end point 3 of interval [2,3], and interval [3,4] do not overlap. Result: [[1,2], [2,3], [3,4]]

  6. All intervals are traversed once, and there are at most 3 non-overlapping intervals. The total number is 4-3 and solution 1 is obtained, that is, at least one interval needs to be removed to make the remaining intervals non-overlapping.

Js code implementation

function eraseOverlapIntervals(intervals) {
    const len = intervals.length;
    if(len <= 1) return 0;
    / / sorting
    intervals.sort((a,b) = > a[1] - b[1]);
    const result = [];
    // Put the first range in the result array
    result.push(intervals[0]);
    for(let i = 1; i < len; i++) {
        // The start of the current range is greater than or equal to the end of the result array range
        if(intervals[i][0] >= result[result.length - 1] [1]) { result.push(intervals[i]); }}return len - result.length;
}
Copy the code

Analyzing time complexity

We need O(nlogn) time to sort all the intervals in ascending order to the right endpoints, and O(n) time to traverse. Since the former is larger than the latter in the asymptotic sense, the total time complexity is O(nlogn).

So the time complexity is: O(n) = nlogn;

conclusion

In this section, we introduce greedy algorithm in detail, and through THE JS code to achieve a variety of classic problems, but also for each topic in the analysis of the topic ideas, JS code implementation, and time complexity analysis. We will find: greedy algorithm is the most important analysis and development of greedy strategy, we must analyze different situations, can see the title quickly confirm whether we should use greedy algorithm, and how to greedy.

Next we will continue to introduce double pointer, DFS, BFS and other interesting algorithms, let’s enjoy the fun of programming!

I am how to celebrate more than years, if the article has helped you, I hope you can point a thumbs-up, thank you!

If you have any questions, please discuss them in the comments section.