We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

IPO

Number: 502

Difficulty: Hard

Paid? No

Companies: Microsoft, Amazon, Meta, Google, Gameskraft, Zeta, PhonePe, Salesforce

Problem Description

Given an initial capital w and a list of n projects (each with its own profit and minimum capital requirement), select at most k distinct projects so that after finishing them sequentially (each project’s profit adding to your capital), your total capital is maximized.

Key Insights

  • Sort the projects by their required capital so that you can easily know which projects are feasible given current capital.
  • Use a max heap (priority queue) to always select the feasible project with the highest profit.
  • Iterate up to k times, each time adding all newly feasible projects (those whose capital requirement is at most the current capital) to the max heap.
  • Terminate early if there are no projects available in the heap.

Space and Time Complexity

Time Complexity: O(n log n + k log n) where n is the number of projects. Space Complexity: O(n) for storing project information and the heap.

Solution

The approach starts by pairing each project’s required capital with its profit, then sorting these pairs based on the capital requirement. For each of the k rounds, add all projects that are affordable (given the current capital) to a max heap that prioritizes profit. Then select the project with the maximum profit, update the available capital and continue. This greedy selection process ensures that the best immediate profit boost is always taken, eventually maximizing the total capital.

Code Solutions

import heapq

def findMaximizedCapital(k, w, profits, capital):
    # Create project pairs (required capital, profit)
    projects = sorted(zip(capital, profits), key=lambda x: x[0])
    max_heap = []  # max heap (simulate by pushing negative profits)
    idx = 0
    n = len(projects)
    
    # Iterate up to k projects
    for _ in range(k):
        # Add all projects that are affordable with current capital w
        while idx < n and projects[idx][0] <= w:
            # Push negative profit to simulate max-heap since heapq is a min-heap
            heapq.heappush(max_heap, -projects[idx][1])
            idx += 1
        
        # If no project is affordable, break out early
        if not max_heap:
            break
        
        # Select project with maximum profit and update capital
        w += -heapq.heappop(max_heap)
    
    return w

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