Блог пользователя dp_is_life

Автор dp_is_life, история, 4 года назад, По-английски

select two non overlapping segment such that sum of their length minimum. O(n) eg. [2,5], [4,6], [6,7]

ans-6 explanation 2 is overlapped with first and third but 1 and 3 is not ans-(5-2+1)+(7-6+1)=6 1<=n<=10^6 timeLimit-1 second

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 9   Проголосовать: нравится +2 Проголосовать: не нравится

What are the constraints on the values of $$$l$$$ and $$$r$$$ (the endpoints of an individual range)?

Anyways, independent of the constraints, I am posting my solution here.

Solution