Posts tagged as “greedy”

花花酱 LeetCode 1833. Maximum Ice Cream Bars

By zxi on April 18, 2021

It is a sweltering summer day, and a boy wants to buy some ice cream bars.

At the store, there are n ice cream bars. You are given an array costs of length n, where costs[i] is the price of the i^th ice cream bar in coins. The boy initially has coins coins to spend, and he wants to buy as many ice cream bars as possible.

Return the maximum number of ice cream bars the boy can buy with coins coins.

Note: The boy can buy the ice cream bars in any order.

Example 1:

Input: costs = [1,3,2,4,1], coins = 7
Output: 4
Explanation: The boy can buy ice cream bars at indices 0,1,2,4 for a total price of 1 + 3 + 2 + 1 = 7.

Example 2:

Input: costs = [10,6,8,7,7,8], coins = 5
Output: 0
Explanation: The boy cannot afford any of the ice cream bars.

Example 3:

Input: costs = [1,6,3,1,2,5], coins = 20
Output: 6
Explanation: The boy can buy all the ice cream bars for a total price of 1 + 6 + 3 + 1 + 2 + 5 = 18.

Constraints:

costs.length == n
1 <= n <= 10⁵
1 <= costs[i] <= 10⁵
1 <= coins <= 10⁸

Solution: Greedy

Sort by price in ascending order, buy from the lowest price to the highest price.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

class Solution {

public:

int maxIceCream(vector<int>& costs, int coins) {

sort(begin(costs), end(costs));

int ans = 0;

for (int c : costs) {

if (c > coins) break;

coins -= c;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1802. Maximum Value at a Given Index in a Bounded Array

By zxi on March 22, 2021

You are given three positive integers n, index and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

nums.length == n
nums[i] is a positive integer where 0 <= i < n.
abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.
The sum of all the elements of nums does not exceed maxSum.
nums[index] is maximized.

Return nums[index] of the constructed array.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: n = 4, index = 2,  maxSum = 6
Output: 2
Explanation: The arrays [1,1,2,1] and [1,2,2,1] satisfy all the conditions. There are no other valid arrays with a larger value at the given index.

Example 2:

Input: n = 6, index = 1,  maxSum = 10
Output: 3

Constraints:

1 <= n <= maxSum <= 10⁹
0 <= index < n

Solution: Binary Search

To maximize nums[index], we can construct an array like this:
[1, 1, 1, …, 1, 2, 3, …, k – 1, k, k – 1, …,3, 2, 1, …., 1, 1, 1]

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxValue(int n, int index, int maxSum) {

int l = 1;

int r = maxSum + 1;

while (l < r) {

int64_t m = l + (r - l) / 2;

int64_t t1 = m - index;

int64_t t2 = m - (n - 1 - index);

int64_t s1 = (t1 + m) * (index + 1) / 2;

int64_t s2 = (m + t2) * (n - index) / 2;

if (t1 <= 0) s1 = (1 + m) * m / 2 + (index - m + 1);

if (t2 <= 0) s2 = (1 + m) * m / 2 + (n - index - m);

if (s1 + s2 - m > maxSum)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 1798. Maximum Number of Consecutive Values You Can Make

By zxi on March 20, 2021

You are given an integer array coins of length n which represents the n coins that you own. The value of the i^th coin is coins[i]. You can make some value x if you can choose some of your n coins such that their values sum up to x.

Return the maximum number of consecutive integer values that you can make with your coins starting from and including 0.

Note that you may have multiple coins of the same value.

Example 1:

Input: coins = [1,3]
Output: 2
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
You can make 2 consecutive integer values starting from 0.

Example 2:

Input: coins = [1,1,1,4]
Output: 8
Explanation: You can make the following values:
- 0: take []
- 1: take [1]
- 2: take [1,1]
- 3: take [1,1,1]
- 4: take [4]
- 5: take [4,1]
- 6: take [4,1,1]
- 7: take [4,1,1,1]
You can make 8 consecutive integer values starting from 0.

Example 3:

Input: nums = [1,4,10,3,1]
Output: 20

Constraints:

coins.length == n
1 <= n <= 4 * 10⁴
1 <= coins[i] <= 4 * 10⁴

Solution: Greedy + Math

We want to start with smaller values, sort input array in ascending order.

First of all, the first number has to be 1 in order to generate sum of 1.
Assuming the first i numbers can generate 0 ~ k.
Then the i+1-th number x can be used if and only if x <= k + 1, such that we can have a consecutive sum of k + 1 by adding x to a sum between [0, k] and the new maximum sum we have will be k + x.

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int getMaximumConsecutive(vector<int>& coins) {

sort(begin(coins), end(coins));

int ans = 0;

for (int c : coins) {

if (c > ans + 1) break;

ans += c;

}

return ans + 1;

}

};

花花酱 LeetCode 1793. Maximum Score of a Good Subarray

By zxi on March 18, 2021

You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 2 * 10⁴
0 <= k < nums.length

Solutions: Two Pointers

maintain a window [i, j], m = min(nums[i~j]), expend to the left if nums[i – 1] >= nums[j + 1], otherwise expend to the right.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumScore(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

for (int i = k, j = k, m = nums[k];;) {

ans = max(ans, m * (j - i + 1));

if (j - i + 1 == n) break;

int l = i ? nums[i - 1] : -1;

int r = j + 1 < n ? nums[j + 1] : -1;

if (l >= r)

m = min(m, nums[--i]);

else

m = min(m, nums[++j]);

}

return ans;

}

};

花花酱 LeetCode 1792. Maximum Average Pass Ratio

By zxi on March 13, 2021

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:

1 <= classes.length <= 10⁵
classes[i].length == 2
1 <= pass_i <= total_i <= 10⁵
1 <= extraStudents <= 10⁵

Solution: Greedy + Heap

Sort by the ratio increase potential (p + 1) / (t + 1) – p / t.

Time complexity: O((m+n)logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

const int n = classes.size();

auto ratio = [&](int i, int delta = 0) {

return static_cast<double>(classes[i][0] + delta) /

(classes[i][1] + delta);

};

priority_queue<pair<double, int>> q;

for (int i = 0; i < n; ++i)

q.emplace(ratio(i, 1) - ratio(i), i);

while (extraStudents--) {

const auto [r, i] = q.top(); q.pop();

++classes[i][0];

++classes[i][1];

q.emplace(ratio(i, 1) - ratio(i), i);

}

double total_ratio = 0;

for (int i = 0; i < n; ++i)

total_ratio += ratio(i);

return total_ratio / n;

}

};

Python3

# Author: Huahua

class Solution:

def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:

def ratio(i, delta=0):

return (classes[i][0] + delta) / (classes[i][1] + delta)

q = []

for i, c in enumerate(classes):

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

for _ in range(extraStudents):

_, i = heapq.heappop(q)

classes[i][0] += 1

classes[i][1] += 1

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

return mean(ratio(i) for i, _ in enumerate(classes))