Source: Spoj.pl
Problem: We have n sticks standing at some points on number line. Location & height of each are given . A single knock( to left or right) of some stick with knock all sticks which it touches. That is if a stick of height h at location h is knocked right , it will knock all sticks at x+1 , x+2....x+h.
Given all sticks' information , Find the minimum number of knocks required to knock all the sticks. We can only spend O(nlogn) time at max.
Link to exact problem page here.
No comments:
Post a Comment