502.IPO.md

502 IPO

题目

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

给定若干个项目。对于每个项目 i，它都有一个纯利润 Pi，并且需要最小的资本 Ci 来启动相应的项目。最初，你有 W 资本。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

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

示例 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。

思路（贪心策略）

准备一个小根堆和一个大根堆。先将所有的项目放进小根堆，小根堆的堆顶为堆中cost最小的项目。然后让所有cost小于W的项目（即当前可以做的项目）进大根堆，大根堆的堆顶为profit最大的项目。每次从大根堆里取出项目做，每做完项目取得收益后W会更新，这时就会有新的项目从小根堆进入到大根堆。当做满了k个项目或者大根堆中没有项目可做时，结束。

每次在所有项目中找利润最高的项目做，是一种贪心策略。也符合生活中面临此类问题时的常规做法。

代码

class Solution {
    //Project项目类包含两个实例域，p代指利润，c代指花销
    public static class Project{
        public int p;
        public int c;
        public Project(int p, int c){
            this.p = p;
            this.c = c;
        }
    }
    //定义一个比较器，根据项目的花销值c比较Project（花销值小的Project小）
    public static class MinCostComparator implements Comparator<Project>{
        @Override
        public int compare(Project o1, Project o2) {
            return o1.c - o2.c;
        }
    }
    //定义一个比较器，根据项目的利润值p比较Project（利润值高的Project小）
    public static class MaxProfitComparator implements Comparator<Project>{
        @Override
        public int compare(Project o1, Project o2) {
            return o2.p - o1.p;
        }
    }

    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        //定义一个项目数组并将其初始化
        Project[] projects = new Project[Profits.length];
        for(int i = 0; i < Profits.length; i++){
            projects[i] = new Project(Profits[i], Capital[i]);
        }
        //准备两个堆，一个堆顶表示堆中cost最小的项目，另一个堆顶表示堆中profit最大的项目
        PriorityQueue<Project> minCostHeap = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Project> maxProfitHeap = new PriorityQueue<>(new MaxProfitComparator());
        for(Project item: projects){
            minCostHeap.add(item);
        }
        for(int i = 0; i < k; i++){
            //小根堆堆顶依次弹出进大根堆，直到堆顶大于w，遇到了没有足够资金做的项目为止
            while(!minCostHeap.isEmpty() && minCostHeap.peek().c <= W)
                maxProfitHeap.add(minCostHeap.poll());
            //循环结束时有两种可能，一种为已经做完了k个项目，另一种为没做到k个项目但能做到项目都做完了
            if(maxProfitHeap.isEmpty())
                return W;
            W += maxProfitHeap.poll().p;
        }
        return W;
    }
}