Maximize Capital

Data Structures and Algorithms

Statement

Given initial capital c, and two lists capitals and profits of length n with values corresponding by index i, find the maximum cumulative capital by selecting at most k projects to invest in.

In order to invest in a project, the current capital must be greater than or equal to its capital requirement.

When a selected project completes, its profit and the starting capital is returned and added to the cumulative capital. Then, another project can be invested in. However, a project can only be invested in once.

Constraints

• 1 ≤ k ≤ 10³
• 0 ≤ c ≤ 10⁹
• 1 ≤ n ≤ 10³
• k ≤ n
• profits.length() == n
• capitals.length() == n
• 0 ≤ profits[i] ≤ 10⁴
• 0 ≤ capitals[i] ≤ 10⁹

Solution

"""
production algorithm
"""

from data_structures.heap.heap import Heap


class Solution:
    def maximum_capital(self, c, k, capitals, profits):
        """
        time complexity O(nlogn)
        space complexity O(n)
        """
        n = len(capitals)
        min_capitals, max_profits = Heap(), Heap()
        result = c

        # sort project capitals lowest to highest
        for i in range(n):
            min_capitals.push(MinHeapData(capitals[i], i))

        for i in range(k):

            # sort available project profits highest to lowest
            while not min_capitals.empty() and min_capitals.top().capital <= result:
                _, index = min_capitals.pop()
                max_profits.push(MaxHeapData(profits[index]))

            # add maximum available profit to cumulative capital
            if max_profits.empty():
                return result
            profit = max_profits.pop().profit
            result = result + profit

        return result


class MinHeapData:
    def __init__(self, capital, index):
        self.capital = capital
        self.index = index

    def __lt__(self, other):
        return self.capital < other.capital

    def __iter__(self):
        yield self.capital
        yield self.index

    def __len__(self):
        return 2


class MaxHeapData:
    def __init__(self, profit):
        self.profit = profit

    def __lt__(self, other):
        return other.profit < self.profit

"""
unit tests
"""

from unittest import TestCase
from algorithms.two_heaps.maximize_capital.solution import Solution


class SolutionTestCase(TestCase):
    def test_zero_capital(self):
        # Given
        c = 0
        k = 25
        capitals = [25, 35, 45, 55, 65]
        profits = [125, 135, 145, 155, 165]
        solution = Solution()

        # When
        actual = solution.maximum_capital(c, k, capitals, profits)

        # Then
        expected = 0
        self.assertEqual(actual, expected)

    def test_cumulative_capital_less_than_all_project_capitals(self):
        # Given
        c = 10
        k = 25
        capitals = [25, 35, 45, 55, 65]
        profits = [125, 135, 145, 155, 165]
        solution = Solution()

        # When
        actual = solution.maximum_capital(c, k, capitals, profits)

        # Then
        expected = 10
        self.assertEqual(actual, expected)

    def test_cumulative_capital_less_than_some_project_capitals(self):
        # Given
        c = 10
        k = 25
        capitals = [5, 115, 335, 445, 555, 665]
        profits = [105, 215, 435, 545, 655, 765]
        solution = Solution()

        # When
        actual = solution.maximum_capital(c, k, capitals, profits)

        # Then
        expected = 330
        self.assertEqual(actual, expected)

    def test_cumulative_capital_greater_than_all_project_capitals(self):
        # Given
        c = 105
        k = 25
        capitals = [15, 25, 35, 45, 55]
        profits = [75, 85, 95, 105, 115]
        solution = Solution()

        # When
        actual = solution.maximum_capital(c, k, capitals, profits)

        # Then
        expected = 580
        self.assertEqual(actual, expected)

    def test_cumulative_capital_bound_by_maximum_number_of_projects(self):
        # Given
        c = 105
        k = 3
        capitals = [15, 25, 35, 45, 55]
        profits = [75, 85, 95, 105, 115]
        solution = Solution()

        # When
        actual = solution.maximum_capital(c, k, capitals, profits)

        # Then
        expected = 420
        self.assertEqual(actual, expected)

Strategy

Two Heaps.

Explanation

First, sort all project capitals lowest to highest in a min heap. The minimum capitals heap is used to find what project can be invested in given the current available capital. Next, iterate at most k projects, or the maximum number of allowed projects. For each iteration, pop all available capitals from the minimum capitals heap, and push their corresponding profit to a max profits heap, sorted highest to lowest. At the end of each iteration, pop from the maximum profits heap and add the maximum available profit to the cumulative capital. Repeat iteration until k projects have been completed, or no more projects are available.

Time Complexity

The algorithm has two main iterations. The first iteration has length n and sorts all capitals in a min heap. The time complexity of the first iteration is O(nlogn). The second iteration has length k, but at worst must sort all profits in a max heap. So at worst, the time complexity of the second iteration is O(nlogn). Therefore the time complexity of the algorithm is O(nlogn).

Space Complexity

The auxiliary space complexity of the algorithm depends on the size of the heaps used. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/two_heaps/maximize_capital at main ·…