A difficult interval problem

Revision en5, by Mopriestt, 2022-07-29 16:08:37

I saw this on AIO 2020 and have no idea.

On an interval ranged 1 ~ L there are N segments (Ai, Bi)

You can add at most k extra segments with length X.

What is the longest continuous interval you can get that is covered by segments?

2 <= L <= 10^9

0 <= k <= 10^9

N <= 10^5

sample

Tags intervals

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Mopriestt 2022-07-29 16:08:37 27 Tiny change: ' 10^5\n\n[Your text to link here...](/predown' -> ' 10^5\n\n[sample](/predown'
en4 English Mopriestt 2022-07-29 16:08:17 94 (published)
en3 English Mopriestt 2022-07-29 16:05:46 4
en2 English Mopriestt 2022-07-29 16:05:33 4 Tiny change: ' <= 10^9\n0 <= k <= 10^9\nN <= 10^' -> ' <= 10^9\n\n0 <= k <= 10^9\n\nN <= 10^'
en1 English Mopriestt 2022-07-29 16:04:42 325 Initial revision (saved to drafts)