Skip to main content

IPO

Problem Description​

Problem StatementSolution LinkLeetCode Profile
IPOIPO Solution on LeetCodeNikita Saini

Problem Description​

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it. Initially, you have w capital. When you finish a project, you obtain its pure profit, which is added to your total capital.

Your goal is to pick a list of at most k distinct projects to maximize your final capital.

Constraints​

  • 1 <= k <= 10^5
  • 0 <= w <= 10^9
  • 1 <= n <= 10^5
  • 0 <= profits[i] <= 10^4
  • 0 <= capital[i] <= 10^9

Approach​

The problem can be approached using a combination of greedy strategy and efficient data structures:

  1. Priority Queue (Max-Heap): Use a max-heap to always select the project with the maximum profit that can be started with the current capital.
  2. Sorting: Sort projects based on their capital requirements.
  3. Iterative Selection: Iterate up to k times (or until no more projects can be started) to select the project with the highest profit that can be started with the current capital.

Solution in Different languages​

Solution in Python​

import heapq

def findMaximizedCapital(k, w, profits, capital):
    n = len(profits)
    projects = sorted(zip(capital, profits))  # Sort projects by their capital requirements
    available_projects = []
    idx = 0
    for _ in range(k):
        while idx < n and projects[idx][0] <= w:
            heapq.heappush(available_projects, -projects[idx][1])  # Max-heap for profits
            idx += 1
        if available_projects:
            w -= heapq.heappop(available_projects)  # Add the profit from the best project
        else:
            break
    return w

# Example usage:
k = 2
w = 0
profits = [1, 2, 3]
capital = [0, 1, 1]
print(findMaximizedCapital(k, w, profits, capital))  # Output: 4

Solution in Java​

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][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, (a, b) -> a[0] - b[0]); // Sort projects by their capital requirements
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        int idx = 0;
        for (int i = 0; i < k; i++) {
            while (idx < n && projects[idx][0] <= w) {
                maxHeap.offer(projects[idx][1]); // Max-heap for profits
                idx++;
            }
            if (!maxHeap.isEmpty()) {
                w += maxHeap.poll(); // Add the profit from the best project
            } else {
                break;
            }
        }
        return w;
    }
}

Solution in C++​

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int, int>> projects(n);
        for (int i = 0; i < n; ++i) {
            projects[i] = {capital[i], profits[i]};
        }
        sort(projects.begin(), projects.end()); // Sort projects by their capital requirements
        priority_queue<int> maxHeap;
        int idx = 0;
        for (int i = 0; i < k; ++i) {
            while (idx < n && projects[idx].first <= w) {
                maxHeap.push(projects[idx].second); // Max-heap for profits
                ++idx;
            }
            if (!maxHeap.empty()) {
                w += maxHeap.top(); // Add the profit from the best project
                maxHeap.pop();
            } else {
                break;
            }
        }
        return w;
    }
};

Solution in C​

#include <stdlib.h>

// Helper function to sort projects by capital requirement
int compare(const void *a, const void *b) {
    int *projA = *(int **)a;
    int *projB = *(int **)b;
    return projA[0] - projB[0];
}

int findMaximizedCapital(int k, int w, int* profits, int profitsSize, int* capital, int capitalSize) {
    int n = profitsSize;
    int **projects = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; ++i) {
        projects[i] = (int *)malloc(2 * sizeof(int));
        projects[i][0] = capital[i];
        projects[i][1] = profits[i];
    }
    qsort(projects, n, sizeof(int *), compare); // Sort projects by their capital requirements
    int idx = 0;
    for (int i = 0; i < k; ++i) {
        while (idx < n && projects[idx][0] <= w) {
            w += projects[idx][1]; // Add the profit from the best project
            ++idx;
        }
        if (idx == n) break;
    }
    for (int i = 0; i < n; ++i) {
        free(projects[i]);
    }
    free(projects);
    return w;
}

Solution in JavaScript​

class PriorityQueue {
    constructor(comparator = (a, b) => a - b) {
        this._heap = [];
        this._comparator = comparator;
    }

    size() {
        return this._heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    peek() {
        return this.isEmpty() ? undefined : this._heap[0];
    }

    push(...values) {
        values.forEach(value => {
            this._heap.push(value);
            this._siftUp();
        });
        return this.size();
    }

    pop() {
        const poppedValue = this.peek();
        const bottom = this.size() - 1;
        if (bottom > 0) {
            this._swap(0, bottom);
        }
        this._heap.pop();
        this._siftDown();
        return poppedValue;
    }

    _parent(idx) {
        return Math.floor((idx - 1) / 2);
    }

    _left(idx) {
        return idx * 2 + 1;
    }

    _right(idx) {
        return idx * 2 + 2;
    }

    _swap(i, j) {
        [this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]];
    }

    _greater(i, j) {
        return this._comparator(this._heap[i], this._heap[j]) < 0;
    }

    _siftUp() {
        let node = this.size() - 1;
        while (node > 0 && this._greater(node, this._parent(node))) {
            this._swap(node, this._parent(node));
            node = this._parent(node);
        }
    }

    _siftDown() {
        let node = 0;
        while (
            (this._left(node) < this.size() && this._greater(this._left(node), node)) ||
            (this._right(node) < this.size() && this._greater(this._right(node), node))
        ) {
            let maxChild = (this._right(node) < this.size() && this._greater(this._right(node), this._left(node))) ? this._right(node) : this._left(node);
            this._swap(node, maxChild);
            node = maxChild;
        }
    }
}

var findMaximizedCapital = function(k, w, profits, capital) {
    const n = profits.length;
    const projects = [];
    for (let i = 0; i < n; i++) {
        projects.push([capital[i], profits[i]]);
    }
    projects.sort((a, b) => a[0] - b[0]); // Sort projects by their capital requirements
    const maxHeap = new PriorityQueue((a, b) => b - a);
    let idx = 0;
    for (let i = 0; i < k; i++) {
        while (idx < n && projects[idx][0] <= w) {
            maxHeap.push(projects[idx][1]); // Max-heap for profits
            idx++;
        }
        if (!maxHeap.isEmpty()) {
            w += maxHeap.pop(); // Add the profit from the best project
        } else {
            break;
        }
    }
    return w;
};

Step-by-Step Algorithm​

  1. Input Parsing: Convert input data into appropriate data structures (arrays, lists, or vectors).
  2. Sorting: Sort projects based on their capital requirements.
  3. Priority Queue Initialization: Initialize a max-heap (priority queue) to keep track of the most profitable projects that can be started with the current capital.
  4. Iterative Selection:
    • For up to k times, iterate through the sorted projects.
    • Push all feasible projects (capital requirement <= current capital) into the max-heap.
    • If the max-heap is not empty, pop the project with the maximum profit and add its profit to the current capital.
    • Break the loop if no more projects can be started.
  5. Return Result: Return the current capital after selecting up to k projects.

Conclusion​

The provided solutions efficiently solve the problem of selecting at most k projects to maximize capital using a combination of greedy strategy and priority queues. This approach ensures that the solution is optimal and runs within acceptable time limits for the given constraints.