502. IPO

Title description:

Let’s say LeetCode is about to launch an IPO. In order to sell the shares to venture capital firms at a higher price, Lico hopes to carry out projects to boost its capital before the IPO. With limited resources, it can only complete a maximum of K different projects before the IPO. Help Lico design the way to get the maximum total capital after completing up to K different projects.

I give you n items. For each project I, there is a net profit [I] and the minimum capital[I] required to start the project.

Initially, your capital was W. When you complete a project, you will make a net profit and the profit will be added to your total capital.

In summary, select a list of up to K different projects from a given project to maximize the final capital and output the maximum capital ultimately available.

The answer is guaranteed to be in the range of 32 – bit signed integers.

Example 1:

Profits = 0, capital = [0,1, 2], capital = [0,1,1] At the end of that, you'll make a profit of 1, and your total capital will be 1. At this point you can choose to start project 1 or 2. Since you can choose up to two projects, you need to complete project 2 to get the most capital. So the final maximum capital output is 0 + 1 + 3 = 4.Copy the code

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2Copy the code

Answer:

C + + :

1. Merge capital and profits into key value pairs and sort by capital values.

A large root heap is used to store values of w+profits in a priority queue. If you want to queue profits of any value in a large root heap, you can queue profits of any value in a priority queue. If you want to queue profits of any value in a priority queue, you can queue profits of any value in a large queue.

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        vector<pair<int.int>> st;
        for(int i=0; i<capital.size(a); ++i){ st.push_back(pair<int.int>(capital[i],profits[i])); // Merge the key-value pairs into a vector
        }
        sort(st.begin(),st.end());/ / sorting
        int ans=w;
        int addr=0;
        priority_queue<int, vector<int>, less<int>> pq;// The priority queue is stored at maximum profits of W +profits
        for(int i=0; i<k; ++i){while(addr<profits.size()&&st[addr].first<=ans){
                pq.push(st[addr].second);// Push the returns
                addr++;
            }

            if(! pq.empty()){
                ans+=pq.top(a);// Take the maximum and add
                pq.pop(a); }else{
                break; }}returnans; }};Copy the code

😀 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions! 🩲 warehouse address: a daily series