Suppose LeetCode will start its ipO soon. In order to sell a good PRice of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at mostk distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at mostk distinct projects.

You are given several projects. For each project i, it has a pure profitP_i and a minimum capital of C_i is needed to start the corresponding project. Initially, you haveW capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:

Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].Output: 4Explanation: Since your initial capital is 0, you can only start the project indexed 0.             After finishing it you will obtain profit 1 and your capital becomes 1.             With capital 1, you can either start the project indexed 1 or the project indexed 2.             Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.             Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Note:
You may assume all numbers in the input are non-negative integers.The length of Profits array and Capital array will not exceed 50,000.The answer is guaranteed to fit in a 32-bit signed integer.
Subscribe to see which companies asked this question.
初始資金為W，最多進(jìn)行k次項(xiàng)目，后面給出n個(gè)項(xiàng)目的收益和需要的資金，問最大的收益。用貪心算法。對于每一次項(xiàng)目，都選最優(yōu)的做，即選擇需要資金小于或等于當(dāng)前資金的項(xiàng)目中收益最大的。為了減少搜索的時(shí)間，用兩個(gè)優(yōu)先隊(duì)列，其中pq1按需要資金從小到大排序，一開始存放全部的項(xiàng)目（項(xiàng)目用（需要資金，收益）來表示）；另一個(gè)pq2按收益 從大到小排序，存放當(dāng)前能做的項(xiàng)目。對于某一次選擇，將pq1中需要資金小于等于當(dāng)前資金的項(xiàng)目pop出來push進(jìn)pq2，然后選擇pq2的top項(xiàng)目（也要pop出來），該項(xiàng)目就是當(dāng)前最佳的項(xiàng)目。
代碼：
class Solution{public:	int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital)	{		auto cmp1 = [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool { return lhs.first > rhs.first; };		priority_queue<pair<int, int>, vector<pair<int, int> >, function<bool (const pair<int, int>&, const pair<int, int>&)> > pq1(cmp1);		auto cmp2 = [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool { return lhs.second < rhs.second; };		priority_queue<pair<int, int>, vector<pair<int, int> >, function<bool (const pair<int, int>&, const pair<int, int>&)> > pq2(cmp2);		for(int i = 0; i < Profits.size(); ++i)		{			pq1.push(pair<int, int>(Capital[i], Profits[i]));		}		int res = W;		while(--k >= 0)		{			while(!pq1.empty() && pq1.top().first <= res)			{				pq2.push(pq1.top());				pq1.pop();			}			if(pq2.empty()) break;			res += pq2.top().second;			pq2.pop();		}		return res;	}};