samurai123's blog

How to solve Hotels problem on Spoj with binary search
By samurai123, history, 8 years ago, In English

I have solved the problem LINK with sliding window. But in comments, some people mentioned about solving it with binary search. What should be the search function for binary search in the problem? Can that function be made without using concept of sliding window.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use binary search on the prefix sum and find the length of segment for each segment starting at position i. Time complexity is O(NlogN), I am not sure if there is another approach using binary search with a more decent time complexity though.

→ Reply