largest-values-from-labels

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given <code>n</code> item&#39;s value and label as two integer arrays <code>values</code> and <code>labels</code>. You are also given two integers <code>numWanted</code> and <code>useLimit</code>.

Your task is to find a subset of items with the maximum sum of their values such that:

<ul>
	<li>The number of items is at most <code>numWanted</code>.</li>
	<li>The number of items with the same label is at most <code>useLimit</code>.</li>
</ul>

Return the maximum sum.

&nbsp;
Example 1:

<div class="example-block">
Input: values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

Output: 9

Explanation:

The subset chosen is the first, third, and fifth items with the sum of values 5 + 3 + 1.
</div>

Example 2:

<div class="example-block">
Input: values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

Output: 12

Explanation:

The subset chosen is the first, second, and third items with the sum of values 5 + 4 + 3.
</div>

Example 3:

<div class="example-block">
Input: values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

Output: 16

Explanation:

The subset chosen is the first and fourth items with the sum of values 9 + 7.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>n == values.length == labels.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= values[i], labels[i] &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= numWanted, useLimit &lt;= n</code></li>
</ul>

第 141 场周赛

weekly-contest-141

largestValsFromLabels

资深工程师

Largest Values From Labels

Maximize Y‑Sum by Picking a Triplet of Distinct X‑Values

maximize-ysum-by-picking-a-triplet-of-distinct-xvalues

选择不同 X 值三元组使 Y 值之和最大

Greedy

Array

Hash Table

Counting

Sorting

以两个整数数组 &nbsp;<code>values</code>&nbsp;和 <code>labels</code>&nbsp;给定&nbsp;<code>n</code>&nbsp;个项的值和标签，并且给出两个整数&nbsp;<code>numWanted</code>&nbsp;和 <code>useLimit</code> 。

你的任务是从这些项中找到一个值的和 最大 的子集使得：

<ul>
	<li>项的数量 最多 为&nbsp;<code>numWanted</code>。</li>
	<li>相同标签的项的数量&nbsp;最多 为&nbsp;<code>useLimit</code>。</li>
</ul>

返回最大的和。

&nbsp;

示例 1：

<div class="example-block">
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1

输出：9

解释：

选择的子集是第一个、第三个和第五个项，其值之和为 5 + 3 + 1。
</div>

示例 2：

<div class="example-block">
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2

输出：12

解释：

选择的子集是第一个、第二个和第三个项，其值之和为 5 + 4 + 3。
</div>

示例 3：

<div class="example-block">
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1

输出：16

解释：

选择的子集是第一个和第四个项，其值之和为 9 + 7。
</div>

&nbsp;

提示：

<ul>
	<li><code>n == values.length == labels.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= values[i], labels[i] &lt;= 2 * 104</code></li>
	<li><code>1 &lt;= numWanted, useLimit &lt;= n</code></li>
</ul>