IPO

Leetcode Problem 502: IPO

Problem Summary

A company wants to maximize its capital before an IPO by completing at most k projects. There are n projects available, each requiring a minimum starting capital and yielding a fixed profit upon completion. You start with w capital; completing a project adds its profit to your current capital, which can unlock additional projects.

Pick at most k distinct projects (in any order) to maximize your final capital. Return the maximum capital achievable. The answer is guaranteed to fit in a 32-bit signed integer.

Constraints:

• You can select at most k projects, with k up to 100,000.
• Initial capital w can be up to 1,000,000,000.
• There are up to 100,000 projects; each project's profit is between 0 and 10,000, and its required capital is between 0 and 1,000,000,000.

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

Projects:
  idx 0: requires capital ≥ 0,  profit = 1
  idx 1: requires capital ≥ 1,  profit = 2
  idx 2: requires capital ≥ 1,  profit = 3

Step 1 (w=0): affordable → {idx 0}
              pick highest profit → idx 0  →  w = 0+1 = 1

Step 2 (w=1): affordable → {idx 1, idx 2}
              pick highest profit → idx 2  →  w = 1+3 = 4

Final capital = 4

Techniques

• Array
• Greedy
• Sorting
• Heap (Priority Queue)

Solution

import {Heap} from "../heap";

type Project = {
    capital: number;
    profits: number;
}

function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number {
    const minCapital = new Heap<Project>((a, b) => a.capital - b.capital)
    const maxProfits = new Heap<Project>((a, b) => b.profits - a.profits)

    for (let i = 0; i < capital.length; i++) {
        minCapital.insert({ capital: capital[i], profits: profits[i] })
    }

    let currentCapital = w

    for (let i = 0; i < k; i++) {
        while (minCapital.size() > 0 && minCapital.peek()!.capital <= currentCapital) {
            maxProfits.insert(minCapital.extract()!)
        }

        if (maxProfits.size() === 0) {
            break;
        }

        currentCapital = currentCapital + maxProfits.extract()!.profits
    }

    return currentCapital
}

console.log(findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1])) // Output: 4