454 views
2 votes
2 votes

$N$ detectors are installed along the edge of a road of length $L$ at different positions (position[N]). Each detector has some predefined range (range[N]) of coverage along the length of the road as shown in the figure below. Detectors are powerful enough to cover the full width of the road.

The optimum time complexity to find the minimum no of detectors to be switched on to cover the full road of length $L$ is

$\begin{align*} &A.&O(N) \\ &B.& O(N^2)\\ &C.& O(N\log N)\\ &D.& \text{NONE}\\ \end{align*}$

1 Answer

3 votes
3 votes
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)
edited by

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
Sajal Mallick asked Nov 27, 2023
171 views
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n l...