DevExCode

LeetCode 502: IPO

ArrayGreedySortingHeap (Priority Queue)

Problem Description

Explanation

To maximize the final capital after finishing at most k distinct projects, we can follow the following approach:

  1. Create a list of projects sorted by their capital requirements.
  2. Maintain a priority queue (max heap) to store the profits of the available projects.
  3. Iterate k times:
    • While iterating, check if any project's capital requirement is less than or equal to the current capital. If so, add its profit to the priority queue.
    • Select the project with the maximum profit from the priority queue and update the current capital.
  4. Repeat the above step k times to select the best k projects to maximize the final capital.

Time Complexity: O(nlogn + klogn) where n is the number of projects
Space Complexity: O(n)

View on LeetCode

Solutions

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<int[]> pqCapital = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pqProfit = new PriorityQueue<>((a, b) -> b - a);

        int n = profits.length;
        int currCapital = w;

        for (int i = 0; i < n; i++) {
            pqCapital.offer(new int[]{capital[i], profits[i]});
        }

        for (int i = 0; i < k; i++) {
            while (!pqCapital.isEmpty() && pqCapital.peek()[0] <= currCapital) {
                pqProfit.offer(pqCapital.poll()[1]);
            }

            if (pqProfit.isEmpty()) {
                break;
            }

            currCapital += pqProfit.poll();
        }

        return currCapital;
    }
}

Related LeetCode Problems

Previous ProblemNext Problem

Loading editor...