Greedy Algorithm

Greedy algorithms or ideas use greedy strategies to ensure that each operation is locally optimal, so that the final result is globally optimal.

455 Distribute biscuits

Title Description

(Simple)
Suppose you're a great parent and you want to give your children some cookies. However, each child can only give one cookie at most.

For each child i, there is an appetite value g[i], which is the minimum size of cookies that will satisfy their appetite. And each biscuit 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 the maximum number.

For example: you have three children and two cookies and three children have appetite values of 1,2,3. Although you have two cookies, because they are all 1 size, you can only satisfy a child with an appetite value of 1. So you should output 1.

Questions:

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        // First sort your child's appetite and cookie size from small to large
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        // Define Initial Value
        int child = 0;
        int cookie = 0;
        // Traverse from small to large, using smaller cookies gives preference to smaller appetite children
        // If
        while(child < g.size() && cookie < s.size()) {
            if(g[child] <= s[cookie]) ++child;
            ++cookie;
        }
        return child;
    }
};

435 No overlap interval

Title Description

(Medium)
Given a set of intervals, find the minimum number of intervals that need to be removed so that the remaining intervals do not overlap each other.

Be careful:
It can be thought that the end point of an interval is always greater than its start point.
The boundaries of the intervals [1,2] and [2,3] touch each other but do not overlap each other.

Problem

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        // Return null if input is null
        if (intervals.empty()){
            return 0;
        }
        int n = intervals.size();
        // Sort the input intervals by sorting them from smallest to largest on the right side of the interval
        // Define sorting using Lambda
        // Lambda expressions are defined as [External variable access specifier] (parameter table) ->Return value type {statement block}
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
            return a[1]<b[1];
        });
        // Define the initial value, initialize to the first interval
        int total = 0, prev = intervals[0][1];
        // Traverse, if the left value of the latter interval is less than the right value of the previous interval, it needs to be removed, otherwise the prev will be updated
        for (int i = 1; i<n; i++){
            if(intervals[i][0] < prev){
                total++;
            }else{
                prev = intervals[i][1];
            }
        }
        return total;
    }
};

135 Distribute Candy

Title Description

(Difficulty)
Teachers want to distribute candy to children. N children stand in a straight line. Teachers will pre-rate each child based on their performance.

You need to help teachers distribute candy to these children as follows:

Each child is assigned at least one candy.
A child with a higher score must get more candy than his neighbour on either side.

So how many candies does the teacher need to prepare at least?

Problem

Initialize the number of candies for all children to 1; Traverse from left to right first. If the score of the right child is higher than that of the left child, the number of candy of the right child is updated to the number of candy of the left child plus 1; Traverse again from right to left, if the score of the left child is higher than that of the right child, and the number of candies in the left child is not greater than that in the right child, the number of candies in the left child is updated to the number of candies in the right child plus one.

class Solution {
public:
    int candy(vector<int>& ratings) {
        // One child returns one
        int size = ratings.size();
        if(size < 2){
            return size;
        }
        // Initialized as an array of length size and value of 1
        vector<int> num(size, 1);
        // Traversing from left to right, if the score of the right child is higher than that of the left child, the number of candies of the right child is updated to the number of candies of the left child plus one
        for(int i = 1; i < size; i++){
            if(ratings[i] > ratings[i-1]){
                num[i] = num[i-1] + 1;
            }
        }
        // Traversing from right to left, if the score of the left child is higher than that of the right child, and the number of candies the left child currently has is not greater than that of the right child,
        // Update the number of candies for the left child to the number of candies for the right child plus 1
        for(int i = size - 1; i > 0; i--){
            if(ratings[i] < ratings[i-1]){
                // Return directly to the maximum number of candies in the left child plus one in the right child
                num[i-1] = max(num[i-1], num[i] + 1);
                // num[i] = num[i-1] + 1;
            }
        }
        // Add all the elements of the array to get the result
        return accumulate(num.begin(), num.end(), 0);
        //accumulate is defined in #include<numeric>, and the third parameter is the initial value
    }
};