**Observation :** There should be a snake in each row and in each column in the range **[(n-k)/2+1,(n+k)/2]**. So we will treat horizontally aligned snakes and vertically aligned snakes separately.(Note that vertically aligned snake also covers one cell horizontally and vice versa).

Let `p1 = (n-k)/2+1`

and `p2 = (n+k)/2`

, *H* be the array that stores (start,end) for the horizontally aligned snakes, i.e. the starting column(start) and the ending column of a snake(end) and *ans* be a variable that stores the minimum number of snakes required.

**Greedy Approach :**

- Sort the array
*H*according to the starting column(start). - Let a variable
*en*be the end point of the snake we have chosen(initially we have not chosen any snake) and*mn*be the farthest end point of the snake that starts before or at*en + 1*.*en*is initialized to*p1 - 1*as we do not need any snake in the range**[0,p1-1]**. - While traversing through array
*H*, there will be 3 cases : - When
*H[i].start <= en+1*, we just need to update*mn = max(mn,H[i].end)*. - When
*H[i].start >en+1*and*mn=en*,that means there will be atleast one column(*(en+1)th column*) left uncovered. So it is impossible to protect the poison and answer is -1. - When
*H[i].start >en+1*and*mn>en*, then we know that we can reach atmost till the*(mn)th*column by choosing a snake. So we will simply update*mn = en*and increment the number of snakes required,i.e.*ans*. - We will traverse through
*H*till*en*reaches to*p2*(because we dont need any snake in the range**[p2+1,n]**. - After traversal, if
*en < p2*, that means it is impossible and hence answer is -1.

Similarly, we can apply the same approach for vertically aligned snakes.

**Correctness :**

Consider 2 varibales *i*,*j* such that, *H[i].start<=en+1*, *H[j].start<=en+1* and *H[i].end < H[j].end*. Then the number of elements *k*(*k > i* and *k < j*) that can be traversed by choosing ith snake is a subset of the number of elements traversed by choosing jth element. Hence it is optimal to choose the jth snake(and hence updating *en=mn*). Thus the greedy approach is correct.

For implementation details, check my solution.

**Complexity :**

*O(NlogN)*