Задача: 502. IPO
Сложность: hard

LeetCode планирует IPO и хочет увеличить капитал, выполняя проекты. У компании ограниченные ресурсы, поэтому она может завершить до k проектов. Помогите LeetCode максимизировать капитал после завершения этих проектов.
У вас есть n проектов с чистой прибылью profits[i] и минимальным капиталом capital[i] для начала.
Изначально у вас есть капитал w. Завершив проект, вы получаете его прибыль, которая добавляется к вашему капиталу.
Выберите до k проектов, чтобы максимально увеличить капитал, и верните его окончательное значение. Ответ гарантированно поместится в 32-битное целое число.

Пример:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

👨‍💻 Алгоритм:

1⃣Сортировка и инициализация
Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста.

2⃣Выбор проектов
Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм.

3⃣Увеличение капитала
Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован.

😎 Решение:

class MaxHeap {
    constructor(compare) {
        this.heap = [];
        this.compare = compare;
    }

    insert(value) {
        this.heap.push(value);
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compare(this.heap[index], this.heap[parentIndex]) <= 0) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    extract() {
        const max = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            let index = 0;
            const length = this.heap.length;
            while (true) {
                let left = 2 * index + 1;
                let right = 2 * index + 2;
                let largest = index;

                if (left < length && this.compare(this.heap[left], this.heap[largest]) > 0) largest = left;
                if (right < length && this.compare(this.heap[right], this.heap[largest]) > 0) largest = right;
                if (largest === index) break;
                [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
                index = largest;
            }
        }
        return max;
    }

    get size() {
        return this.heap.length;
    }
}

const findMaximizedCapital = (k, w, profits, capital) => {
    const projects = capital.map((cap, i) => [cap, profits[i]]).sort((a, b) => a[0] - b[0]);
    const maxHeap = new MaxHeap((a, b) => b - a);
    let ptr = 0;

    for (let i = 0; i < k; i++) {
        while (ptr < projects.length && projects[ptr][0] <= w) {
            maxHeap.insert(projects[ptr][1]);
            ptr++;
        }
        if (maxHeap.size === 0) break;
        w += maxHeap.extract();
    }

    return w;
};

Ставь 👍 и забирай 📚 Базу знаний