[LeetCode]IPO

题目描述:

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 Pi and a minimum capital of Ci 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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. 西雅图 西雅图 发布于 2017年3月7日 07:44 #

    书影大牛,感谢你心血收集这么多的题。

    但是这道题用greedy正确吗?比如,假设有projects如下,格式是(capital,profit)。(1,1),(2,3),(2,3),(4,5),初始capital是4。如果每次选profit最高的,那我们只能找到(4,5)。但其实最优应该是(2,3)+(2,3)。这题有点象0/1 backpack的衍生,可能要用DP才行?

    或者我理解有误?

  2. 在线疯狂 在线疯狂 发布于 2017年3月7日 17:52 #

    题意理解的有误,再仔细阅读一下题目描述。

  3. 西雅图 西雅图 发布于 2017年3月8日 08:50 #

    再次拜读,我忘记了profit can be converted into capital once project is done.

    但是我又再想想,好像下面这个例子还是不对。比如projects有(40,10),(20,5),(20,6),初始capital是40,需要找2个。如果是greedy,一开始选(40,10),我们就只能选1个。但是,(20,5)加(20,6)更好?

  4. 在线疯狂 在线疯狂 发布于 2017年3月8日 10:08 #

    题目大意是:给定一组项目收益Profits,项目所需的最小启动资金Capital。最多可以完成的项目数k,以及初始启动资金W。求至多完成k个项目时,资金的最大值。
    对于你提供的测试用例,首先选择40, 10;然后选择20, 6

  5. 西雅图 西雅图 发布于 2017年3月9日 02:00 #

    哦,这下懂了。题目的意思是capital不会减少,只会增加(从完成project的profit来)。这也太坑爹了。这是考语文啊。或者出题的意思是要你和面官clarify。leetcode的题好像越来越懒啊。

张贴您的评论