Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Maximize Capital

Problem Statement

Given a set of investment projects with their respective profits, we need to find the most profitable projects. We are given an initial capital and are allowed to invest only in a fixed number of projects. Our goal is to choose projects that give us the maximum profit. Write a function that returns the maximum total capital after selecting the most profitable projects.

We can start an investment project only when we have the required capital

.....

.....

.....

Like the course? Get enrolled and start learning!
W

Will

· 4 years ago

The time complexity should maybe just be simplified (to avoid confusion with other sources i.e. Leetcode Q502: IPO) from: O(NlogN + KlogN) to O(NlogN).

Because in the worst/ largest case of 'K' (num of projects), since we can't re-pick projects, K's worst case would just be N, since we can't pick more projects than there are projects available to choose from (since projects are not un-bounded). Therefore, it's really O(NlogN + NlogN) in the worst case 'K' value, which is O(NlogN).

Show 1 reply