10148 - Advertisement

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
triplemzim
New poster
Posts: 48
Joined: Sat Apr 06, 2013 6:02 pm

Re: 10148 - Advertisement

Post by triplemzim » Thu Sep 11, 2014 6:54 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10148 - Advertisement

Post by brianfry713 » Fri Sep 12, 2014 2:37 am

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”