A difficult interval problem

Правка en2, от Mopriestt, 2022-07-29 16:05:33

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

some sample:

Теги intervals

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский 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 Английский Mopriestt 2022-07-29 16:08:17 94 (published)
en3 Английский Mopriestt 2022-07-29 16:05:46 4
en2 Английский 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 Английский Mopriestt 2022-07-29 16:04:42 325 Initial revision (saved to drafts)