10148 - Advertisement

[triplemzim]

What is the algorithm for solving this kind of problem? Can this be solved using Binary Indexed Tree?

[brianfry713]

You can solve it using a greedy strategy.
Sort the intervals by non-decreasing end.
For each interval, if the length is <= K then put a billboard at every location.
Otherwise place billboards at the largest unused location within that interval until at least K billboards have been placed inside it.