咨询：求满足约束条件的最大非重叠合格子集数量的算法

核心思路 #

要得到最多满足要求的子集，核心逻辑是尽可能用最少的元素组成一个和≥Y的子集——因为每少用一个元素，就能给剩余元素留出更多组成新子集的机会。

具体实现步骤 #

1. 排序预处理
   先将所有元素按从小到大排序，方便后续双指针操作。
2. 双指针贪心策略
   • 用左指针left指向当前最小元素，右指针right指向当前最大元素。
   • 优先检查最大元素：如果当前最大元素单独≥Y，直接将其作为一个独立子集，计数加1，右指针左移一位。
   • 若最大元素单独不满足，从最小元素开始累加，直到加上最大元素的总和≥Y：此时将这些元素组成一个子集，计数加1，左指针移动到累加后的位置，右指针左移一位。
   • 若累加所有剩余元素仍无法达到Y，直接终止循环，剩余元素无法组成有效子集。
3. 关键注意点
   只要最大元素加最小元素的和≥Y，就优先配对这两个元素（用2个元素组成子集），避免浪费更多小元素；只有当两者之和不够时，才继续添加更多小元素。

示例验证（以集合[1,1,1,1,1,7,8]，Y=5为例） #

排序后集合：[1,1,1,1,1,7,8]

• 第一步：最大元素8≥5，单独作为子集，计数=1，右指针移至7的位置。
• 第二步：7≥5，单独作为子集，计数=2，右指针移至最后一个1的位置。
• 第三步：当前最大元素是1，单独不够，累加剩余所有1，总和=5≥5，组成一个子集，计数=3。
  最终得到3个子集，远优于“大元素配小元素”方法得到的2个。

伪代码实现 #

def max_valid_subsets(nums, target):
    nums.sort()
    left = 0
    right = len(nums) - 1
    subset_count = 0
    
    while left <= right:
        # 优先单独取大元素
        if nums[right] >= target:
            subset_count += 1
            right -= 1
            continue
        
        # 累加小元素直到和达标
        current_sum = nums[right]
        temp_left = left
        while temp_left < right and current_sum < target:
            current_sum += nums[temp_left]
            temp_left += 1
        
        if current_sum >= target:
            subset_count += 1
            left = temp_left
            right -= 1
        else:
            # 剩余元素无法凑出达标和，终止
            break
    
    return subset_count

为什么旧方法会次优 #

之前的“为最大数字寻找最优组合”方法，会优先将大元素与小元素配对，导致原本可以单独成子集的大元素被浪费了配对名额，剩余的小元素可能无法凑出达标和，最终总子集数更少。比如上述示例中，旧方法会把8和1配对、7和1配对，剩下3个1无法凑出≥5的和，只能得到2个子集。

内容的提问来源于stack exchange，提问作者Matheus Beraldo