Leetcode-SEVEN-Greedy

Leetcode-SEVEN-Greedy
- IPO
  - Description
  - Example
  - Analysis
  - Code

IPO

Description

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

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.

Analysis

题目意思就是，在给定初始资产因子 W，希望完成的任务数 k 和任务的利润数组 Profits 和所需资产因子数组 Capital 的情况下，求解出完成 k 个任务后，所积累的最大资产因子。

这是非常典型的贪心算法。我们每一轮完成任务，选取本次可选任务利润最高的，循环至无可完成任务，则可以保证最终结果是最佳的。至于证明，可以利用归纳法：

在倒数第一轮，我们拥有前面 k - 1 轮能得到的最优资产因子 max，剩余的可选任务利益为 $[p1, p2, p3, …, pn]$，所需资产因子为 $[w1, w2, w3, …, wn]$，并且有 $pi > pj(i < j)，w_{max} = max [w1, w2, w3, …, wn] < max$。很明显，我们必然选取 p1，因为我们只能完成最后一个任务，而为了让累计资产因子最大，选取利益最大的任务，也就是 p1。
那么，对于倒数第 i 轮，我们拥有前面 k - i 轮能得到的最优资产因子 $max_i$，剩余的可选任务利益为 $[p_i1, p_i2, p_i3, …, p_in]$，所需资产因子为 $[w_i1, w_i2, w_i3, …, w_in]$，同时 $pm > pn(m < n)，w_{i}max = max [w_i1, w_i2, w_i3, …, w_in] < max_i$。那么，在这时，我们同样选取 $p_i1$，以达到倒数第 i-1 轮能取到的最优 max 资产因子。归纳后，我们可以得到，在第一轮就根据这个方法进行选择，可以在最终得到我们需要的最优解。

在这里，当然可能存在多组解，考虑这个情况：w = 0， k = 3，Profits = [1, 1, 1, 1]，Capital = [0, 0, 0, 0]，那么我们最终结果都是3，但每次选取谁都是一样的，这就是多解。幸运的是，我们并不关注多解情况，我们只关注最终结果。所以，这对算法没有影响。那么我们就设计出了完成这个题目的贪心算法：每次选取当前轮数获利最大的任务完成，直至任务数满足或无任务可做

细节的话，我们可以这么考虑：

采用一个优先队列 low，存储当前轮数可完成的任务利益，每轮从里面选择一个最大的来完成；
采用一个vector high，存储当前所有不可完成的任务，每轮完成一个任务，从中把所有的下一轮可完成的加入优先队列 low；

Code

static int desyncio = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    if (b.first == a.first) return b.second > a.second;
    return b.first > a.first;
}

class Solution {
public:
  
  int findMaximizedCapital(int &count, int &max, vector<int>& Profits, vector<int>& Capital) {
    vector<pair<int, int> > high;
    priority_queue<int> low;
    for (int index = 0; index < Profits.size(); ++index) {
      if (Profits[index] > 0) {
        if (Capital[index] <= max) {
          low.push(Profits[index]);
        }
        else {
            high.push_back({Capital[index], Profits[index]});
        }
      }
    }

    sort(high.begin(), high.end(), cmp);

    while(count && low.size()) {
      max += low.top();
      low.pop();
      --count;
      
      auto i = high.begin();
      while (i != high.end() && i->first <= max) {
        low.push(i->second);
        i = high.erase(i);
      }
    }
    
    return max;
  }
};