502. IPO - 力扣（LeetCode）

一、题目

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释：
由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

二、代码

class Solution {
    // 项目类
    public static class Program {
        public int profit;
        public int capital;
        public Program(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }
    // 对成本做小根堆
    public static class ProgramComparatorCapital implements Comparator<Program> {
        @Override
        public int compare(Program a, Program b) {
            return a.capital - b.capital;
        }
    }
    // 对利润做大根堆
    public static class ProgramComparatorProfit implements Comparator<Program> {
        @Override
        public int compare(Program a, Program b) {
            return b.profit - a.profit;
        }
    }
    // 使用贪心求解
    // 过程就是先按照成本从小到大排列好，然后将所有当前自己可以做的项目拿出来
    // 将这些项目拿出来之后再按照利润从大到小排序，选利润最大的那个做
    // 按照这个流程直到昨晚k个项目或者资金已经不足以再做项目了即可结束，最后得到最大的利润
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 判空直接返回0
        if (profits == null || capital == null || profits.length == 0 || capital.length == 0) {
            return 0;
        }
        // 创建成本的小根堆和利润的大根堆
        PriorityQueue<Program> pqCapital = new PriorityQueue<>(new ProgramComparatorCapital());
        PriorityQueue<Program> pqProfit = new PriorityQueue<>(new ProgramComparatorProfit());
        // 先将所有的项目加入到成本小根堆中
        for (int i = 0; i < profits.length; i++) {
            Program p = new Program(profits[i], capital[i]);
            pqCapital.add(p);
        }
        // 记录已经做了多少个项目了
        int cnt = 0;
        // 当已经做了k个项目则结束循环
        while (cnt < k) {
            // 将成本小根堆中所有在现有资金下可以进行的项目全部弹出放入到利润大根堆中
            // 当小根堆为空或者现有资金下已经没有项目能做，则结束循环
            while (!pqCapital.isEmpty() && pqCapital.peek().capital <= w) {
                Program p = pqCapital.peek();
                // 只要是当前资金超过这个项目的成本就弹出放入到大根堆中
                pqCapital.poll();
                pqProfit.add(p);
            }
            // 将利润大根堆中的堆顶弹出，我们在所有可以做的项目中选出利润最大的项目来做
            Program doProgram = pqProfit.poll();
            // 如果大根堆中弹出项目，则更新现有资金，并且记录上已经做的项目个数
            if (doProgram != null) {
                cnt++;
                w += doProgram.profit;
            // 如果大根堆中已经没有项目弹出了，说明所有的可以做的项目已经做完了，则直接结束循环    
            } else {
                break;
            }
        }
        // 返回最大利润
        return w;
    }
}

三、解题思路 

1、首先理解题意，就是在有限的资金和有限的能做的项目个数的限制下，选取要做的项目使最终的利润最大。

2、在理解了题意之后，就需要找到一个正确的贪心策略。这个题目的贪心策略还是很简单的，其实就按照我们在日常生活中碰到这种问题时的思路去求解就行。我们手里的资金是固定的，我们就将所有的项目按照需要的资金从小到大排序，从这里面把自己当前能够做的项目全都找出来。然后再将这些项目按照利润从大到小排序，找利润最大的项目做，这样自己手里的资金就更新了，再按照这个过程继续去挑选，最终当做完k个项目或者资金已经不足以再做剩余项目的时候，获得的利润就是最大的。