IPO

Problem Description

Problem Statement	Solution Link	LeetCode Profile
IPO	IPO Solution on LeetCode	Nikita 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.