C++算法精讲之贪心算法

void swap(int* arr, int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void selectSort(int* arr, int n)
{
	//降序
	for (int i = 0; i < n; i++)
	{
		int maxIndex = i;
		for (int j = i+1; j < n; j++)
		{
			if (arr[j] >= arr[maxIndex])
				maxIndex = j;
		}
		swap(arr, i, maxIndex);
	}
}

class Solution {
public:
    int balancedStringSplit(string s) {
        if(s.size() == 1)
            return 0;
        int cnt = 0;
        int balance = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == 'R')
                --balance;
            else 
                ++balance;
            if(balance == 0)
                cnt++;
        }
        if(cnt == 0)
            return 1;

        return cnt;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(int i = 0; i < prices.size() - 1; i++)
        {
            if(prices[i] <= prices[i+1])
                profit += prices[i+1] - prices[i];
        }

        return profit;
    }
};

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxLen = nums[0];
        for(int i = 0; i < nums.size(); i++)
        {
            if(i <= maxLen)
            {
                maxLen = max(i + nums[i],maxLen);
                if(maxLen >= nums.size() - 1)
                    return true;
            }
        }

        return false;
    }
};

//按面值降序
struct cmp {
	bool operator()(vector<int>& a1, vector<int>& a2) {
		return a1[0] > a2[0];
	}
};

int solve(vector<vector<int>>& moneyCount, int money)
{
	int num = 0;
	sort(moneyCount.begin(), moneyCount.end(), cmp());
	//首先选择最大面值的纸币
	for (int i = 0; i < moneyCount.size() - 1; i++)
	{
		//选择需要的当前面值和该面值有的数量中的较小值
		int c = min(money / moneyCount[i][0], moneyCount[i][1]);
		money -= c * moneyCount[i][0];
		num += c;
	}
	if (money > 0)
		num = -1;
	return num;
}

struct cmp{
	bool operator()(const int& x, const int& y){
		return x > y;
	}
};

int findMax(vector<int>& Machines)
{
	int ret = 0;
	for (int i = 0; i < machines.size(); i++)
	{
		if (machines[i] > machines[ret])
			ret = i;
	}

	return machines[ret];
}

int greedStrategy(vector<int>& works, vector<int>& machines)
{
	//降序
	sort(works.begin(), works.end(), cmp());
	int n = works.size();
	int m = machines.size();
	for (int i = 0; i < n; i++)
	{
		int finish = 0;
		int machineTime = machines[finish];
		for (int j = 1; j < m; j++)
		{
			if (machines[j] < machines[finish])
			{
				finish = j;
			}
		}
		machines[finish] += works[i];
	}

	return findMax(machines);
}

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

int getMaxNum(vector<vector<int>>& events)
{
	sort(events.begin(), events.end(), cmp());
	int num = 1;
	int i = 0;
	for (int j = 1; j < events.size();j++)
	{
		if (events[j][0] >= events[i][1])
		{
			++num;
			i = j;
		}
	}

	return num;
}

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapintervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp());
        int num = 1;
        int i = 0;
        for(int j = 1; j < intervals.size(); j++)
        {
            if(intervals[j][0] >= intervals[i][1])
            {
                i = j;
                num++;
            }
        }

        return intervals.size() - num;
    }
};

struct cmp{
	bool operator()(vector<int>& s1, vector<int>& s2){
		return s1[1] < s2[1];
	}
};

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        sort(intervals.begin(), intervals.end(), cmp());
        int prev = 0;
        int num = 0;
        for(int i = 1; i < intervals.size(); i++)
        {
            //情况1 不冲突
            if(intervals[i][0] >= intervals[prev][1])
            {
                prev = i;
            }
            else
            {
                if(intervals[i][1] < intervals[prev][1])
                {
                    //情况2
                    prev = i;
                }
                num++;
            }
        }

        return num;
    }
};