502.ipo.md

502. IPO

Heap (Greedy)

• If we have enough capital, we add all projects which capital <= capital to the max heap as candidates. Since we want to maximize the profit, we use a max heap, and we want to filter out the projects which capital <= capital, so we sort the projects by capital.
• We select the project with the maximum profit from the max heap and add the profit to the capital.
• We repeat the above steps until we have selected k projects or the max heap is empty.

data class Project(
    val profit: Int,
    val capital: Int
)

class Solution {
    fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capitals: IntArray): Int {
        val n = profits.size
        val projects = Array<Project>(n) {
            Project(
                profits[it],
                capitals[it]
            )
        }
        projects.sortBy { it.capital }
        val maxHeap = PriorityQueue<Project>() { p1, p2 -> p2.profit - p1.profit }
        var projectIndex = 0
        var capital = w
        var times = 0
        while (projectIndex < n && projects[projectIndex].capital <= capital) {
            maxHeap.add(projects[projectIndex++])
        }
        while (times < k && maxHeap.isNotEmpty()) {
            val project = maxHeap.poll()
            capital += project.profit
            while (projectIndex < n && projects[projectIndex].capital <= capital) {
                maxHeap.add(projects[projectIndex++])
            }
            times++
        }
        return capital
    }
}

• Time complexity: O(nlogn + klogn)
• Space complexity: O(n)