Minimum number of towers required such that every house is in the range of at least one tower | Function to count the number of tower ; first we sort the house numbers ; for count number of towers ; for iterate all houses ; count number of towers ; find find the middle location ; traverse till middle location ; this is point to middle house where we insert the tower ; now find the last location ; traverse till last house of the range ; return the number of tower ; given elements ; print number of towers
< ? php function number_of_tower ( $ house , $ range , $ n ) { sort ( $ house ) ; $ numOfTower = 0 ; $ i = 0 ; while ( $ i < $ n ) { $ numOfTower ++ ; $ loc = $ house [ $ i ] + $ range ; while ( $ i < $ n && $ house [ $ i ] <= $ loc ) $ i ++ ; -- $ i ; $ loc = $ house [ $ i ] + $ range ; while ( $ i < $ n && $ house [ $ i ] <= $ loc ) $ i ++ ; } return $ numOfTower ; } $ house = array ( 7 , 2 , 4 , 6 , 5 , 9 , 12 , 11 ) ; $ range = 2 ; $ n = sizeof ( $ house ) / sizeof ( $ house [ 0 ] ) ; echo number_of_tower ( $ house , $ range , $ n ) ; ? >