IPO-贪心

题目

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

示例

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

算法

在可以做的前提下，优先做钱多的项目。
做完项目后资本增加
一个纯利润大根堆，一个资本小根堆
将满足资本小于等于已有资本的项目从小根堆出拿出放入大根堆，取堆顶项目做。

代码

class Solution {
    public class Project{
        private int profit;
        private int capital;

        public Project(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }
    public class MaxProfit implements Comparator {
        public int compare(Project o1, Project o2) {
            return o2.profit - o1.profit;
        }
    } 
    public class MinCapital implements Comparator {
        public int compare(Project o1, Project o2) {
            return o1.capital - o2.capital;
        }
    }   
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue maxProfit = new PriorityQueue<>(new MaxProfit());
        PriorityQueue minCapital = new PriorityQueue<>(new MinCapital());
        
        for (int i = 0; i < profits.length; i++) {
            minCapital.add(new Project(profits[i], capital[i]));
        }

        for (int i = 0; i < k; i++) {
            while (!minCapital.isEmpty() && minCapital.peek().capital <= w) {
                maxProfit.add(minCapital.poll());
            }
            if (maxProfit.isEmpty()) {
                return w;
            }
            w += maxProfit.poll().profit;
        }
        return w;
    }
}