Skip to content

Greedy from Smallest Largest

Table of Contents

3074. Apple Redistribution into Boxes

from typing import List


# Greedy
def minimumBoxes(apple: List[int], capacity: List[int]) -> int:
    target = sum(apple)
    capacity.sort(reverse=True)
    res = 0

    for box in capacity:
        res += 1
        target -= box
        if target <= 0:
            break

    return res


apple = [1, 3, 2]
capacity = [4, 3, 1, 5, 2]
assert minimumBoxes(apple, capacity) == 2

#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

class Solution
{
public:
    int minimumBoxes(vector<int> &apple, vector<int> &capacity)
    {
        int s = accumulate(apple.begin(), apple.end(), 0);
        sort(capacity.begin(), capacity.end(), greater<int>());

        int i = 0;
        while (s > 0)
        {
            s -= capacity[i++];
        }
        return i;
    }
};

int main()
{
    Solution s;
    vector<int> apple = {1, 3, 2};
    vector<int> capacity = {4, 3, 1, 5, 2};
    cout << s.minimumBoxes(apple, capacity) << endl;
    return 0;
}

2279. Maximum Bags With Full Capacity of Rocks

1833. Maximum Ice Cream Bars

1005. Maximize Sum Of Array After K Negations

"""
-   Return the maximum sum of the array after changing at most `k` elements.
"""

from heapq import heapify, heapreplace
from typing import List


# Greedy
def largestSumAfterKNegationsGreedy(nums: List[int], k: int) -> int:
    nums.sort(key=abs, reverse=True)

    for i in range(len(nums)):
        if nums[i] < 0 and k > 0:
            nums[i] *= -1
            k -= 1

    if k % 2:
        nums[-1] *= -1

    return sum(nums)


# Heap
def largestSumAfterKNegationsHeap(nums: List[int], k: int) -> int:
    heapify(nums)

    while k and nums[0] < 0:
        heapreplace(nums, -nums[0])
        k -= 1

    if k % 2:
        heapreplace(nums, -nums[0])

    return sum(nums)


print(largestSumAfterKNegationsGreedy([4, 2, 3], 1))  # 5
print(largestSumAfterKNegationsHeap([4, 2, 3], 1))

1481. Least Number of Unique Integers after K Removals

1403. Minimum Subsequence in Non-Increasing Order

3010. Divide an Array Into Subarrays With Minimum Cost I

1338. Reduce Array Size to The Half

1710. Maximum Units on a Truck

3075. Maximize Happiness of Selected Children

from typing import List


# Greedy
def maximumHappinessSum(happiness: List[int], k: int) -> int:
    selected = 0
    happinessScore = 0
    happiness.sort(reverse=True)

    for score in happiness:
        if selected == k:
            return happinessScore
        happinessScore += max(0, score - selected)
        selected += 1

    return happinessScore


happiness = [1, 2, 3]
k = 2
print(maximumHappinessSum(happiness, k))  # 4

2554. Maximum Number of Integers to Choose From a Range I

2126. Destroying Asteroids

2587. Rearrange Array to Maximize Prefix Score

976. Largest Perimeter Triangle

1561. Maximum Number of Coins You Can Get

3301. Maximize the Total Height of Unique Towers

945. Minimum Increment to Make Array Unique

from typing import List


# Greedy
def minIncrementForUnique(nums: List[int]) -> int:
    nums.sort()
    moves = 0

    for i in range(1, len(nums)):
        if nums[i] <= nums[i - 1]:
            moves += nums[i - 1] + 1 - nums[i]
            nums[i] = nums[i - 1] + 1

    return moves


nums = [1, 2, 2]
print(minIncrementForUnique(nums))  # 1

1846. Maximum Element After Decreasing and Rearranging

1647. Minimum Deletions to Make Character Frequencies Unique

2971. Find Polygon With the Largest Perimeter

2178. Maximum Split of Positive Even Integers

2567. Minimum Score by Changing Two Elements

1509. Minimum Difference Between Largest and Smallest Value in Three Moves

3397. Maximum Number of Distinct Elements After Operations

3457. Eat Pizzas!

1262. Greatest Sum Divisible by Three

948. Bag of Tokens

1775. Equal Sum Arrays With Minimum Number of Operations

2333. Minimum Sum of Squared Difference

3440. Reschedule Meetings for Maximum Free Time II

2141. Maximum Running Time of N Computers

1196. How Many Apples Can You Put into the Basket

2214. Minimum Health to Beat Game

2098. Subsequence of Size K With the Largest Even Sum

2548. Maximum Price to Fill a Bag

3119. Maximum Number of Potholes That Can Be Fixed

2557. Maximum Number of Integers to Choose From a Range II

624. Maximum Distance in Arrays

from typing import List


# Array
def maxDistance(arrays: List[List[int]]) -> int:
    mn, mx = float("inf"), float("-inf")
    res = 0

    for arr in arrays:
        res = max(res, arr[-1] - mn, mx - arr[0])
        mn = min(mn, arr[0])
        mx = max(mx, arr[-1])

    return res


arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]
print(maxDistance(arrays))  # 4

910. Smallest Range II

2835. Minimum Operations to Form Subsequence With Target Sum

3366. Minimum Array Sum

Comments