At CellForge Bio, each iPSC colony has a quality score. You need to form as many differentiation batches as possible while ensuring every batch meets a minimum efficiency requirement.
Given an array scores, where scores[i] is the quality score of the ith colony, and an integer threshold, form batches such that each colony is used at most once and each batch is valid if:
batch_size * minimum_score_in_batch >= threshold
Return the maximum number of valid batches that can be formed.
scores: list of integersthreshold: integerExample 1
scores = [3, 1, 9, 6], threshold = 82[1, 3, 6, 9]. Batch [9] is valid because 1 * 9 >= 8. Batch [3, 6] is valid because 2 * 3 = 6 is not enough, but [1, 3, 6] gives 3 * 1 = 3, still invalid. The optimal grouping is [9] and [1, 3, 6] is invalid, so instead use [6, 3]? That also fails. The best valid grouping is [9] and [6, 3, 1] invalid, so only one? However, using descending greedy gives [9] and [6, 3] invalid, [6, 3, 1] invalid. Therefore output is 1.Example 2
scores = [4, 4, 4, 4], threshold = 822 * 4 = 8.1 <= len(scores) <= 10^51 <= scores[i] <= 10^91 <= threshold <= 10^9scores = [3, 1, 9, 6], threshold = 8Output1WhyAfter sorting to `[9, 6, 3, 1]`, batch `[9]` is valid. No remaining grouping reaches the threshold, so the maximum is 1.scores = [4, 4, 4, 4], threshold = 8Output2WhyTwo batches of size 2 can be formed, and each has minimum score 4, so `2 * 4 = 8`.scores = [10, 10, 10], threshold = 5Output3WhyEach colony alone forms a valid batch because `1 * 10 >= 5`.1 <= len(scores) <= 10^51 <= scores[i] <= 10^91 <= threshold <= 10^9def max_valid_batches(scores, threshold):