Why is the greedy algorithm optimal?

Question

Codility, lesson 14, task TieRopes (https://codility.com/demo/take-sample-test/tie_ropes). Stated briefly, the problem is to partition a list A of positive integers into the maximum number of (contiguous) sublists having sum at least K.

I've only come up with a greedy solution because that's the name of the lesson. It passes all the tests but I don't know why it is an optimal solution (if it is optimal at all).

int solution(int K, vector<int> &A) {
    int sum = 0, count = 0;
    for (int a : A)
    {
        sum += a;
        if (sum >= K)
        {
            ++count;
            sum = 0;
        }
    }
    return count;
}

Can somebody tell me if and why this solution is optimal?

Answer 1

Maybe I'm being naive or making some mistake here, but I think that is not too hard (although not obvious) to see that the algorithm is indeed optimal.

Suppose that you have an optimal partition of the list that with the maximum number of sublists. You may or may not have all of the elements of the list, but since adding an element to a valid list produces an also valid lists, lets suppose that any possible "remaining" element that was initially not assigned to any sublist was assigned arbitrarily to one of its adjacent sublists; so we have a proper optimal partition of the list, which we will call P1.

Now lets think about the partition that the greedy algorithm would produce, say P2. There are two things that can happen for the first sublist in P2:

1. It can be the same as the first sublist in P1.
2. It can be shorter than the first sublist in P1.

In 1. you would repeat the reasoning starting in the next element after the first sublist. If every subsequent sublist produced by the algorithm is equal to that in P1, then P1 and P2 will be equal.

In 2. you would also repeat the reasoning, but now you have at least one "extra" item available. So, again, the next sublist may:

2.1. Get as far as the next sublist in P1.
2.2. End before the next sublist in P1.

And repeat. So, in every case, you will have at least as many sublists as P1. Which means, that P2 is at least as good as any possible partition of the list, and, in particular, any optimal partition.

It's not a very formal demonstration, but I think it's valid. Please point out anything you think may be wrong.