IPO

IPO

Suppose you are given k projects to maximize your total capital. You start with an initial capital w. When you complete a project, you earn its pure profit and your capital increases by that amount.

Pick at most k distinct projects from the given list to maximize your final capital.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital requirement capital[i].

Examples

Example 1:

Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4
Explanation:
  Start with w = 0. Choose project 0 (capital needed: 0, profit: 1). Now w = 1.
  Choose project 2 (capital needed: 1, profit: 3). Now w = 4.
  Maximum capital = 4.

Example 2:

Input: k = 3, w = 0, profits = [1, 2, 3], capital = [0, 1, 2]
Output: 6
Explanation:
  Choose project 0 (profit: 1, w = 1), then project 1 (profit: 2, w = 3),
  then project 2 (profit: 3, w = 6).

Constraints

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

Expected Complexity

• Time: O(n log n)
• Space: O(n)