Ok, we can solve this problem in O(nlogn) complexity, with binary search and dynamic programming approach.
Let's see how can we obtained optimal answer to this problem
Let first sort the positon in increasing order.
Then we traverse from left to right ( that is from i = 1 to i = N ) ( i am assuming 1 based indexing )
Let,
F ( i ) ( ON ) : optimal cost till ith position , where detector[i] is in ON state.
F(i)(OFF ) : optimal cost till ith position , such that detecter[i] is in OFF state.
Then what's the recurrence,
cost of F[i][ON] = 1 + F[ j ] [ ON ] , where j < i and we have to consider all index = j , such that position[j] + range[j] >= ( position[i] - range[i] ) and we take min ( F[ j ][ ON ] out of all valid j index ) if that index is not present then cost[ i ] [ ON ] = 1
cost of F[ i ] [ OFF ] = F[ j ] [ ON ] , where j < i and we have to consider all index = j , such that position[j] + range[j] >= position[i] and we take min ( F[ j ][ ON ] out of all valid j index if that index is not present then we cost[ i ] [ OFF ] = INFINITE (Means some large value , because we can't cover ith detector from left )
And at last our answer will be : minimum( F[ N ][ ON ] , F[ N ] [ OFF ] ) where N : last positon.
And for each ith index , the optimal jth index can be find with binary search , or with the help of other data strucrture , their are many ways, we can use segment tree data structure , binary sarch tree.
Then for each index extra logn complexity required.
Overall complexity : Sort + processing : NlogN + NlogN : O( Nlogn)
I don't think so we can solve, it in linear time , sorting is compulsory ofcourse , hence nlogn is already spend.
After that linear will be possible only if we use some sort of greedy approach, but i don't think so that greedy works fine for this problem.
Hence option C is correct : O(NlogN)