IPO — Hard Problem & Solution

You can finish at most k projects before an IPO. Project i needs capital[i] to start and adds profits[i] to your capital when finished (the capital spent is…

Difficulty: Hard
Topics: Arrays, Greedy, Sorting, Heap
Asked at: Amazon, Google, Goldman Sachs
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You can finish at most k projects before an IPO. Project i needs capital[i] to start and adds profits[i] to your capital when finished (the capital spent is returned, so it is pure profit).

Starting with w capital and able to run only one project at a time, return the maximum capital you can end with.

Example 1

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Finish project 0 for 1, then project 2 for 3.

Example 2

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
Explanation: All three become affordable in turn.

Example 3

Input: k = 1, w = 2, profits = [1,2,3], capital = [1,1,2]
Output: 5

Constraints

1 <= k <= 1000
0 <= w <= 1000000000
n == profits.length == capital.length
1 <= n <= 1000
0 <= profits[i] <= 10000
0 <= capital[i] <= 1000000000

How to solve IPO

Greedy with a max-heap. Capital only grows, so the set of affordable projects only grows too — sort by capital and push newly affordable projects into a max-heap keyed on profit, then always take the heap's top.

Approach

Sort the project indices by required capital.
Repeat up to k times: push every project whose capital requirement is now met, then pop the largest profit and add it to the capital.
Stop early if no project is affordable.

Why it works

Taking the most profitable affordable project first is optimal because profits are non-negative, so finishing it never shrinks the affordable set — every project available under any other choice is still available after this one. An exchange argument then turns any optimal schedule into the greedy one. The pointer never moves backwards, so each project is pushed once.

Complexity

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

Pitfalls

Re-scanning all projects for the best affordable one each round is O(k · n) — fine at these limits but the heap is the point.
The loop must break when nothing is affordable, or it spins.
The final capital reaches about 10^9 + 10^7, which still fits int.

Reference solution

Python

import heapq
from typing import List

def findMaximizedCapital(k: int, w: int, profits: List[int], capital: List[int]) -> int:
    n = len(profits)
    order = sorted(range(n), key=lambda i: capital[i])
    heap = []
    ptr, cur = 0, w
    for _ in range(k):
        while ptr < n and capital[order[ptr]] <= cur:
            heapq.heappush(heap, -profits[order[ptr]])
            ptr += 1
        if not heap:
            break
        cur += -heapq.heappop(heap)
    return cur

JavaScript

var findMaximizedCapital = function(k, w, profits, capital) {
    var n = profits.length;
    var idx = [];
    for (var t = 0; t < n; t++) idx.push(t);
    idx.sort(function(a, b) { return capital[a] - capital[b]; });
    var heap = [];
    var push = function(v) {
        heap.push(v);
        var i = heap.length - 1;
        while (i > 0) {
            var p = (i - 1) >> 1;
            if (heap[p] >= heap[i]) break;
            var tmp = heap[p]; heap[p] = heap[i]; heap[i] = tmp;
            i = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var i = 0;
            while (true) {
                var l = 2 * i + 1, r = 2 * i + 2, m = i;
                if (l < heap.length && heap[l] > heap[m]) m = l;
                if (r < heap.length && heap[r] > heap[m]) m = r;
                if (m === i) break;
                var tmp2 = heap[m]; heap[m] = heap[i]; heap[i] = tmp2;
                i = m;
            }
        }
        return top;
    };
    var ptr = 0, cur = w;
    for (var s = 0; s < k; s++) {
        while (ptr < n && capital[idx[ptr]] <= cur) { push(profits[idx[ptr]]); ptr++; }
        if (heap.length === 0) break;
        cur += pop();
    }
    return cur;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue