define

Greedy algorithms (also known as greedy algorithms) are those that always make the best choice for the moment when solving a problem. In other words, instead of thinking about global optimality, what he makes is a local optimal solution in a sense.

Usually greedy algorithms have very short code and very simple ideas, but the real challenge of greedy algorithms is to make sure that we can actually use greedy algorithms for our current problem.

Leetcode 455. Distribute cookies

Their thinking

This is a simple greedy algorithm problem. We try to give the biggest cookie to the most greedy child, and if we can satisfy the most greedy child, we leave the next less greedy child with the biggest cookie. If the biggest cookie can’t satisfy the most greedy child, that means it can’t satisfy the child.

    class Solution {
    public:
        int findContentChildren(vector<int>& g, vector<int>& s) {
    
            sort(g.begin(), g.end(), greater<int> ()); sort(s.begin(), s.end(), greater<int> ());int gi = 0, si = 0;
            int res = 0;
            while( gi < g.size() && si < s.size() ){
    
                if( s[si] >= g[gi] ){
                    res ++;
                    si ++;
                    gi ++;
                } else{ gi ++; }}returnres; }};Copy the code

Greedy algorithms are usually associated with sorting, so if they give us an array that’s not sorted, we have to sort it ourselves.

The relationship between greedy algorithms and dynamic programming

Dynamic programming method

Their thinking

We can start by thinking about the violent solution: find all the combinations of subintervals, and then determine whether it overlaps. Order 2 to the n times n is sorted so it doesn’t overlap.

This problem looks a lot like the longest ascending subsequence. We first solve this problem using dynamic programming:

implementation

    
    
    // Definition for an interval.
    struct Interval {
        int start;
        int end;
        Interval() : start(0), end(0) {}
        Interval(int s, int e) : start(s), end(e) {}
    };
    
    bool compare(const Interval &a, const Interval &b){
    
        if( a.start ! = b.start )return a.start < b.start;
        returna.end < b.end; } // Class Solution {public: int eraseOverlapIntervals(vector<Interval>& intervals) {if( intervals.size() == 0 ) {
                return0; } sort(intervals.begin(), intervals.end(), compare); // The intervals[I] : the intervals[I] : the intervals[I] : the intervals (intervals[I]) : the intervals (intervals[I]) : the intervals (intervals[I]) : the intervals (intervals[I]) : the intervals (intervals[I]);for( int i = 1 ; i < intervals.size() ; i ++ ) {
                // memo[i]
                for( int j = 0 ; j < i ; j ++ ) {
                    if( intervals[i].start >= intervals[j].end ) {
                        memo[i] = max( memo[i] , 1 + memo[j] );
                    }
                }
            }
    
            int res = 0;
            for( int i = 0 ; i < memo.size() ; i ++ ) {
                res = max( res , memo[i] );
            }
    
            returnintervals.size() - res; }};Copy the code

Greedy algorithm solution

Their thinking

Note: In each selection, the end of each interval is important. The smaller the ending, the more room there is for the back, which is more likely to accommodate more sections. Greedy algorithm: Sort by the end of the interval, and select the interval with the earliest end that does not overlap with the previous interval each time.

implementation


    // Definition for an interval.
    struct Interval {
        int start;
        int end;
        Interval() : start(0), end(0) {}
        Interval(int s, int e) : start(s), end(e) {}
    };
    
    bool compare(const Interval &a, const Interval &b){
        if( a.end ! = b.end )return a.end < b.end;
        return a.start < b.start;
    }
    
    // Greedy algorithm
    class Solution {
    public:
        int eraseOverlapIntervals(vector<Interval>& intervals) {
    
            if( intervals.size() == 0 ) {
                return 0;
            }
    
            sort(intervals.begin(), intervals.end(), compare);
    
            int res = 1;
            int pre = 0;
            for( int i = 1 ; i < intervals.size() ; i ++ ) {
                if( intervals[i].start >= intervals[pre].end ){ res ++; pre = i; }}returnintervals.size() - res; }};Copy the code

Proof of the nature of greedy selection

  • The greedy algorithm is A; The optimal algorithm is O; It is found that A can completely replace O without affecting the optimal solution.
  • If greedy algorithms cannot be used, give counterexamples

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato technology small stack and gold digging home page

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan