Topic describes

This is 502. IPO on LeetCode, difficulty is difficult.

Tag: greedy, priority queue, heap

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

Tip:

  • 1 <= k <=
    1 0 5 10^5
  • 0 <= w <=
    1 0 9 10^9
  • n == profits.length
  • n == capital.length
  • 1 <= n <=
    1 0 5 10^5
  • 0 <= profits[i] <=
    1 0 4 10^4
  • 0 <= capital[i] <=
    1 0 9 10^9

Greedy + Priority queue (heap)

Because each task will make the total capital W increase or remain the same. Therefore, for the selected task iii, the most profitable task should be selected from all the “unselected” tasks with no more than W start-up funds.

It can be proved by induction that selecting the most profitable task among all the candidates each time maximizes the total funding.

For the third selection (currently all funds are WWW), if the selected task profit is curcurcur, the actual maximum optional task profit is maxmaxmax (cur<= MAXcur <=maxcur <= Max).

Change “Select Curcurcur” to “Select MaxMaxMax” and the result will not be worse:

  1. According to the transitivity, w+cur<= MAXcur <= maxw+cur<=w+ maxw+cur<=w+ Max can be obtained from cur<= MAXcur <=w+maxw +cur<=w+ Max, and it can be deduced that the adjusted total fund will not be less;
  2. Using corollary 111, since the total funding is not less than before the adjustment, the set of optional tasks will not be less. This means that at least all the original choices after the third selection can be maintained.

So far, we have shown that adjusting each choice to the task of selecting the maximum profit does not make the result worse.

Once you know that you should always choose the most profitable of all the available tasks, look at how the algorithm works.

Since the total funding increases/stays the same for each task completed, the number of task sets that can be covered also increases/stays the same.

Therefore, the core of the algorithm is “before each decision, add the task whose start-up capital does not exceed the current total capital into the set, and then take the task with the maximum profit from it”.

The process of “Max out” can be achieved by using a priority queue (a large root heap sorted by profit), while the operation of “adding tasks to the set whose start-up capital does not exceed the current total capital” can be achieved by pre-sorting all tasks first while the total capital increases throughout the process.

Specifically, we can solve it according to the following process:

  1. Pre-processing the duality of the total task set based on profits and capital, and sorting it in ascending order based on “start-up capital”;

  2. Before each decision, all tasks with startup capital not more than WWW are added to the priority queue (large root heap sorted by profit), and then profits are added to WWW from the priority queue (large root heap sorted by profit);

  3. Step 222 is repeated until KKK tasks are reached or the queue is empty (the current funds are not enough to select any tasks).

Code:

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new int[]{capital[i], profits[i]});
        }
        Collections.sort(list, (a,b)->a[0]-b[0]);
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int i = 0;
        while (k-- > 0) {
            while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]);
            if (q.isEmpty()) break;
            w += q.poll();
        }
        returnw; }}Copy the code
  • Time complexity: the complexity of constructing and sorting a binary array is O(nlog⁡n)O(n\log{n})O(nlogn); The large root heap has at most NNN elements, and the complexity of calculating the answer using the large root heap is O(klog⁡n)O(k\log{n})O(klogn). The overall complexity of O (Max ⁡ (nlog ⁡ n, klog ⁡ n)) O (\ Max (n \ log {n}, k \ log {n})) O (Max (nlogn klogn))
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.502 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.