Sometimes, a seemingly reasonable greedy idea might not work. Your friend is trying to solve the $$Positive Interval

Covering$$ problem:

In an array A of integers, call an interval $($i$,$ j$)$ positive if A$[$i$]+$ A$[$i $+1]++$ A$[$j$]>0.$ Your friend

wishes to $$cover$$ the positive integers of the array with disjoint intervals $($i$.$e$.,$ the intervals may not

overlap$).$ An element is $$covered$$ if it is part of one of the intervals. Given an array A$,$ containing n

integers $($which may be positive, negative, or zero$),$ your friend wants to find the smallest number of

disjoint positive intervals which can cover all the positive elements of A$.$ Note that negative elements

$($and copies of $0)$ may be uncovered, or they may be part of intervals.

Your greedy friend loves using greedy algorithms, and has a greedy idea to solve this problem. Their idea is:

starting from the leftmost positive element, keep a running sum of the elements in the interval as you move the

right endpoint to the right. Move it to the right until the interval becomes non$-$positive, then make everything to

the left the interval.

Your friend$$s idea seems quite reasonable on the surface. Being the great friend you are, you$$ve decided to help

your friend write some pseudocode for their idea. Of course, being the amazing coder that you are, you$$ve perfectly

implemented your friend$$s idea in the following perfectly perfect pseudocode $($which is perfect$)$:

$1$: function PositiveCovering$($A$[1..$n$]))$

$2$: startInd $1$

$3$: while There is a positive element in A at startInd or later do

$4$: while A$[$startInd do $5$: startInd$++6$:

$7$: endInd $$startInd $+1$

$8$: sum $$A$[$startInd$]$

$9$: while sum $>0$ do

$10$: if endInd$=$ n $+1$ then $11$: endInd$++$

$12$: break

$13$: sum $+=$ A$[$endInd$]$

$14$: endInd$++$

$15$: Add $($startInd$...$endInd$-1)$ to list of intervals $16$: startInd $$endInd $-1$ return list of intervals

$$Your friend knows that every greedy idea needs a proof of correctness, and they wrote the following attempt at a

proof of correctness:

Spoof. We prove the claim using the $$greedy stays ahead$$ format.

Let OPT be an optimal solution, and let ALG be the solution generated by our algorithm. We will show that for all n$,$

after the nth interval $($reading from left$-$to$-$right$)$ ALG has covered at least as many positive elements as OPT.

We proceed by induction on n$.$

Base Case: n $=1$

The left$-$most interval must cover the left$-$most positive element. ALG chooses the longest positive interval that

includes that first element $($as it runs until the interval becomes invalid$),$ so it must have at least as many elements

covered as OPT does.

IH: Suppose that the claim holds for n $=1,...,$ k$.$

IS: Let i$...$j be the endpoints of the $($k $+1)$st interval $($from left$-$to$-$right$)$ of OPT. We claim that ALG will cover at

least through index j$.$

Case $1$: ALG was testing starting from i $($that is$,$ index i contained the left$-$most uncovered positive element$)$

Since OPT takes i$,...,$ j as an interval, it must be a positive interval. Thus ALG will consider i$...$j as a valid interval.

It will only choose a different interval if it is longer, since we only ever increase endInd. Thus ALG covers at least

as many elements as OPT.

Case $2$: ALG was testing starting from an index l $=$ i

By IH$,$ ALG covered at least as many elements as OPT in the first k intervals. Thus we have l $>$ i$.$ Observe that any

elements at or after i but strictly before l $($i$.$e$.$ those that OPT covers but ALG does not$)$ will not include any positive

entries, as ALG starts at the first uncovered positive element. Thus, the sum A$[$i$]++$ A$[$j$]$ is at most A$[$l$]++$ A$[$j$].$

Since OPT considers i$...$j a positive interval, l$,...,$ j is also a positive interval, which means that ALG will consider

that interval. Thus ALG also will choose an ending point j or larger.

In both cases, we have shown the claim holds for k $+1,$ as required

$($a$)$ One of your TAs notices your pseudocode and tells you that this greedy idea doesn$$t work. Find a coun$-$

terexample for this algorithm, where your friend$$s seemingly reasonable greedy idea does not work, by

describing an integer array. You should also describe what intervals the provided pseudocode returns, and

describe a better set of intervals $($i$.$e$.$ a way to cover all the positive elements of the array using less disjoint

positive intervals than the greedy solution$).$ You do not need to explain how you found your solution.

$($b$)$ If the idea doesn$$t work, then your friend$$s proof must be wrong! Clearly describe the error in the proof.

A description cannot just be $$the counter$-$example shows it must be wrong.$$ You need to find an incorrect

leap in logic, invalid assumption, missing case, or similar error. Nonetheloess, it will probably help to run the

algorithm on your example with an eye toward the proof to see where it breaks down.

Our explanation is only a few sentences, but it$$s ok if yours is a bit longer.

Part c in image