题目描述：

LeetCode 502. IPO

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 most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit P_i and a minimum capital of C_i is needed to start the corresponding project. Initially, you have W 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: 4

Explanation: 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:

1. You may assume all numbers in the input are non-negative integers.
2. The length of Profits array and Capital array will not exceed 50,000.
3. The answer is guaranteed to fit in a 32-bit signed integer.

题目大意：

给定一组项目收益Profits，项目所需的最小启动资金Capital。最多可以完成的项目数k，以及初始启动资金W。求至多完成k个项目时，资金的最大值。

注意：

1. 你可以假设所有输入数字均为非负整数。
2. 收益数组Profits和启动资金数组Capital的大小均不超过50,000。
3. 答案确保在32位带符号整数范围之内。

解题思路：

贪心算法

在启动资金允许的范围之内，选取收益最大的项目

首先将项目projects按照启动资金从小到大排序（projects为<Capital, Profits>的组合）

记当前资金为ans，初始令ans = W

维护优先队列pq，将所有启动资金不大于ans的收益加入pq

将pq中的最大值弹出并加入ans

循环直到完成k个项目为止

Java代码：

import java.awt.Point;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
        int size = Profits.length;
        int ans = W;
        Point projects[] = new Point[size];
        for (int i = 0; i < projects.length; i++) {
            projects[i] = new Point(Capital[i], Profits[i]);
        }
        Arrays.sort(projects, new Comparator<Point>(){
            public int compare(Point a, Point b) {
                if (a.x == b.x)
                    return a.y - b.y;
                return a.x - b.x;
            }
        });
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
        int j = 0;
        for (int i = 0; i < Math.min(k, size); i++) {
            while(j < size && projects[j].x <= ans) {
                pq.add(projects[j].y);
                j++;
            }
            if (!pq.isEmpty())
                ans += pq.poll();
        }
        return ans;
    }
}

 

本文链接：http://bookshadow.com/weblog/2017/02/05/leetcode-ipo/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码