Skip to main content

502. IPO

hard

Pick at most k projects to maximize capital, where each project requires upfront capital and pays a profit. Two heaps — min by capital, max by profit — make this elegant.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it. 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. Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

Constraints

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

Examples

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.

Example 2

Input
k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output
6

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Greedy: at each of k rounds, pick the highest-profit project you can afford.

Hint 2

Two heaps: a min-heap by required capital (the 'not yet affordable' pool) and a max-heap by profit (the 'affordable now' pool).

Hint 3

Per round: drain everything from the capital-heap whose requirement <= current w into the profit-heap. Then pop the top of the profit-heap and add it to w. If the profit-heap is empty, return early — no project is affordable.

Solution approach

Reveal approach

Push all projects into a min-heap keyed on required capital. Maintain a max-heap keyed on profit. Run k rounds: pop from the min-heap into the max-heap as long as the top's capital requirement is <= current w (i.e., everything you can afford right now). Then pop the top of the max-heap (the most profitable affordable project) and add its profit to w. If the max-heap is empty before you've finished k rounds, return w — there's nothing more you can fund. O((n + k) log n) time, O(n) space. Sorting projects by capital up-front + a single max-heap is an equivalent simplification.

Complexity

Time
O((n + k) log n)
Space
O(n)

Related patterns

  • heap
  • two-heaps
  • greedy
  • sorting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill IPO and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →