Put Marbles in Bags

hard sorting greedy heap prefix sum

Problem

You must split the marbles into k contiguous, non-empty bags. A bag covering indices i..j costs weights[i] + weights[j], and the score is the sum of all bag costs. Return the difference between the maximum and minimum possible scores.

Choosing the bags is equivalent to choosing k − 1 cut points between adjacent marbles. A cut after index i contributes the adjacent pair sum weights[i] + weights[i+1]; the fixed ends weights[0] + weights[n-1] appear in every distribution and cancel out. So we just pick the largest and smallest k − 1 pair sums.

Inputweights = [1,3,5,1], k = 2

Output4

Pair sums are [4, 8, 6]. With k−1 = 1 cut, max = 8 and min = 4, so 8 − 4 = 4.

weights (comma-separated)

k (number of bags)

def put_marbles(weights, k):
    n = len(weights)
    if k == 1 or k == n:
        return 0
    pairs = [weights[i] + weights[i + 1] for i in range(n - 1)]
    pairs.sort()
    m = k - 1
    min_score = sum(pairs[:m])
    max_score = sum(pairs[-m:])
    return max_score - min_score

function putMarbles(weights, k) {
  const n = weights.length;
  if (k === 1 || k === n) return 0;
  const pairs = [];
  for (let i = 0; i < n - 1; i++) pairs.push(weights[i] + weights[i + 1]);
  pairs.sort((a, b) => a - b);
  const m = k - 1;
  let minScore = 0, maxScore = 0;
  for (let i = 0; i < m; i++) minScore += pairs[i];
  for (let i = 0; i < m; i++) maxScore += pairs[n - 2 - i];
  return maxScore - minScore;
}

long putMarbles(int[] weights, int k) {
    int n = weights.length;
    if (k == 1 || k == n) return 0;
    long[] pairs = new long[n - 1];
    for (int i = 0; i < n - 1; i++) pairs[i] = weights[i] + weights[i + 1];
    Arrays.sort(pairs);
    int m = k - 1;
    long minScore = 0, maxScore = 0;
    for (int i = 0; i < m; i++) minScore += pairs[i];
    for (int i = 0; i < m; i++) maxScore += pairs[n - 2 - i];
    return maxScore - minScore;
}

long long putMarbles(vector<int>& weights, int k) {
    int n = weights.size();
    if (k == 1 || k == n) return 0;
    vector<long long> pairs(n - 1);
    for (int i = 0; i < n - 1; i++) pairs[i] = weights[i] + weights[i + 1];
    sort(pairs.begin(), pairs.end());
    int m = k - 1;
    long long minScore = 0, maxScore = 0;
    for (int i = 0; i < m; i++) minScore += pairs[i];
    for (int i = 0; i < m; i++) maxScore += pairs[n - 2 - i];
    return maxScore - minScore;
}

Explanation

The trick is to see that every valid distribution is just a choice of where to make k − 1 cuts between adjacent marbles. Because bags are contiguous, the cut positions fully determine the partition.

Now look at a bag spanning i..j: its cost is weights[i] + weights[j], the two boundary marbles. If you sum the costs over all bags, every internal boundary contributes the pair weights[c] + weights[c+1] for each cut after index c, and the two outer ends weights[0] + weights[n-1] are always present.

So score = weights[0] + weights[n-1] + Σ (chosen adjacent pair sums). The first part is constant, so maximizing or minimizing the score reduces to picking the largest or smallest k − 1 adjacent pair sums.

We build the array of n − 1 pair sums, sort it, take the top k − 1 for the maximum and the bottom k − 1 for the minimum. The constant ends cancel when we subtract, so the answer is simply maxScore − minScore over the selected pair sums.

Sorting is the simplest route; with a heap you could instead extract the k−1 largest and k−1 smallest, which is what makes this a priority-queue style selection problem. Either way the work is dominated by ordering the pair sums.

Time: O(n log n) Space: O(n)