Table of Contents

ExplanationImplementation

Explanation

We can solve this problem using a greedy approach.

The idea is to prioritize projects that offer the highest profit. At the same time, we ensure that the projects we choose can be started with the capital we currently have.

Implementation

Time Complexity: O(Nlog⁡N) \mathcal{O} (N \log N)

C++

class Solution {
  public:
	int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
		const int n = (int)profits.size();


		vector<pair<int, int>> projects(n);
		for (int i = 0; i < n; i++) { projects[i] = {capital[i], profits[i]}; }
		sort(begin(projects), end(projects));


		priority_queue<int> pq;

Java

class Solution {
	public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
		int n = profits.length;


		List<Project> projects = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			projects.add(new Project(capital[i], profits[i]));
		}
		Collections.sort(projects, Comparator.comparingInt(p -> p.capital));

Python

import heapq




class Solution:
	def findMaximizedCapital(
		self, k: int, w: int, profits: List[int], capital: List[int]
	) -> int:
		n = len(profits)
		projects = sorted((capital[i], profits[i]) for i in range(n))

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum