IPO

1package pkg5leetcode.official75;2 3/*4 * IPO | LC 5025 * APPROACH: Sort by capital; max-heap profits unlockable.6 * COMPLEXITY: Time O(n log n), Space O(n)7 */8import java.util.*;9 10public class official75_LC502IPO {11    static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {12        int n = profits.length;13        int[][] projects = new int[n][2];14        for (int i = 0; i < n; i++) { projects[i][0] = capital[i]; projects[i][1] = profits[i]; }15        Arrays.sort(projects, (a, b) -> Integer.compare(a[0], b[0]));16        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());17        int i = 0;18        while (k-- > 0) {19            while (i < n && projects[i][0] <= w) pq.offer(projects[i++][1]);20            if (pq.isEmpty()) break;21            w += pq.poll();22        }23        return w;24    }25 26    public static void main(String[] args) {27        check(findMaximizedCapital(2, 0, new int[]{1,2,3}, new int[]{0,1,1}) == 4, "case1");28        check(findMaximizedCapital(3, 0, new int[]{1,2,3}, new int[]{0,1,2}) == 6, "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}