dp_is_life's blog

Problem
By dp_is_life, history, 4 years ago, In English

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

  • Vote: I like it
  • -16
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
← Rev. 9   Vote: I like it +2 Vote: I do not like it

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
→ Reply