Cloudflare

01Determine Minimum Partitions Required

You were given a list of partitions and partitions used, determine the minimum amount of partitions required to fit all partitions. Data can be moved in chunks. Function Description Complete the function determineMinPartitionsRequired in the editor. determineMinPartitionsRequired has the following parameters:

1. int[] partitions: an array of integers representing the size of each partition
1. int[] partitionsUsed: an array of integers representing the used space in each partition Returns int: the minimum number of partitions required

Example 1

Input:

partitions = [10, 15, 15, 20]
partitionsUsed = [5, 10, 15, 5]

Output:

Explanation: Explanation: 2 partitions of [15, 20] can accommodate [5, 10, 15, 5].

解法

总数据量 S = sum(partitionsUsed)。把 partitions 按容量降序排序，贪心从最大容量开始累加，第一个使累计容量 ≥ S 的分区个数就是答案。排序 O(n log n)，扫描 O(n)。

from typing import List

def determine_min_partitions_required(partitions: List[int], partitions_used: List[int]) -> int:
    need = sum(partitions_used)
    if need == 0:
        return 0
    cap = 0
    for i, p in enumerate(sorted(partitions, reverse=True), 1):
        cap += p
        if cap >= need:
            return i
    return -1  # not enough total capacity

import java.util.*;

class Solution {
    public int determineMinPartitionsRequired(int[] partitions, int[] partitionsUsed) {
        long need = 0;
        for (int u : partitionsUsed) need += u;
        if (need == 0) return 0;
        Integer[] arr = new Integer[partitions.length];
        for (int i = 0; i < partitions.length; i++) arr[i] = partitions[i];
        Arrays.sort(arr, Collections.reverseOrder());
        long cap = 0;
        for (int i = 0; i < arr.length; i++) {
            cap += arr[i];
            if (cap >= need) return i + 1;
        }
        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int determineMinPartitionsRequired(vector<int>& partitions, vector<int>& partitionsUsed) {
        long long need = accumulate(partitionsUsed.begin(), partitionsUsed.end(), 0LL);
        if (need == 0) return 0;
        sort(partitions.begin(), partitions.end(), greater<int>());
        long long cap = 0;
        for (int i = 0; i < (int)partitions.size(); i++) {
            cap += partitions[i];
            if (cap >= need) return i + 1;
        }
        return -1;
    }
};