IPO — codeloopback

NeetCode: IPO · LeetCode: 502. IPO · Difficulty: Hard

You start with capital w and may complete at most k distinct projects. Project i needs capital of at least capital[i] to start and adds profits[i] to your capital when finished. Return the maximum capital you can have after at most k projects.

Example

Text

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

In the first example: do project 0 (capital becomes 1), then project 2 (profit 3, needs 1), ending at 4.

Profits are non-negative, so finishing a project never hurts, and finishing a more profitable one now never blocks anything a smaller profit would allow. That is the greedy insight: at each step, among the affordable projects, take the one with the largest profit. The two solutions below differ only in how they find it.

Brute force: rescan for the best affordable project

Repeat up to k times: scan all unused projects, pick the affordable one with the largest profit, add its profit to w, and mark it used. Stop early if nothing is affordable. Each round is O(n), so this costs O(k * n).

Java

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];
        for (int round = 0; round < k; round++) {
            int best = -1;
            for (int i = 0; i < n; i++) {
                if (!used[i] && capital[i] <= w && (best == -1 || profits[i] > profits[best])) {
                    best = i;
                }
            }
            if (best == -1) {
                break;
            }
            used[best] = true;
            w += profits[best];
        }
        return w;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMaximizedCapital(2, 0, new int[]{1, 2, 3}, new int[]{0, 1, 1}));
        System.out.println(s.findMaximizedCapital(3, 0, new int[]{1, 2, 3}, new int[]{0, 1, 2}));
        System.out.println(s.findMaximizedCapital(5, 0, new int[]{1, 2}, new int[]{1, 1}));
        System.out.println(s.findMaximizedCapital(0, 7, new int[]{1, 2}, new int[]{0, 0}));
    }
}

Output

The third case has no affordable project, and the fourth has k = 0; both leave the capital unchanged. Time: O(k * n). Space: O(n).

Optimal: sort by capital, max-heap of profits

Sort the projects by required capital (pairs of {capital, profit} in an int[][], sorted with Comparator.comparingInt). Keep an index into that order. Each round, move every project that is now affordable (capital <= w) into a max-heap keyed by profit, then poll the top profit (Java's PriorityQueue is a min-heap, so Collections.reverseOrder() makes it a max-heap) and add it to w. Because w only grows, a project that became affordable stays affordable, so the index only moves forward and each project enters the heap once. If the heap is empty, no further project is affordable and the loop stops.

Java

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][];
        for (int i = 0; i < n; i++) {
            projects[i] = new int[]{capital[i], profits[i]};
        }
        Arrays.sort(projects, Comparator.comparingInt(p -> p[0]));
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); // max-heap of profits
        int next = 0;
        for (int round = 0; round < k; round++) {
            while (next < n && projects[next][0] <= w) {
                heap.add(projects[next][1]);
                next++;
            }
            if (heap.isEmpty()) {
                break;
            }
            w += heap.poll();
        }
        return w;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.findMaximizedCapital(2, 0, new int[]{1, 2, 3}, new int[]{0, 1, 1}));
        System.out.println(s.findMaximizedCapital(3, 0, new int[]{1, 2, 3}, new int[]{0, 1, 2}));
        System.out.println(s.findMaximizedCapital(5, 0, new int[]{1, 2}, new int[]{1, 1}));
        System.out.println(s.findMaximizedCapital(0, 7, new int[]{1, 2}, new int[]{0, 0}));
    }
}

Output

w is an int here. If the capital and profits can be large enough that their sum exceeds Integer.MAX_VALUE, w should be a long.

Time: O(n log n + k log n): the sort, plus at most n pushes and k pops. Space: O(n).