Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

Auto comment: topic has been updated by Mopriestt (previous revision, new revision, compare).

Doesn't something simple like two pointers and binary search work here?

We'll use binary search to find out what actual asnwer is and then we'll go through segments considering the begin of our interval is A[i]. We are also going to update pointer to last segment lying in the interval. When moving iterators we'll also count how many segments we need. A little dirty and messy solution but should work anyways.

Sliding window might work

You'd first sort the intervals by A[i], and then merge any touching/overlapping intervals. Then the space between two consecutive intervals i,j would have cost (A[j]-B[i]-1)/X, i.e. the number of extra segments required to fill the gap. Since an optimal solution will always fill consecutive gaps, you could fill the first k gaps and then use sliding window

This is a sketch of a possible $$$O(n \log n)$$$ solution (possibly optimizable to $$$O(n)$$$?).

It's easy to see that we can only consider the ranges that start at $$$a_i$$$ values. For a given start point $$$a_i$$$, we can compute the solution in $$$O(n)$$$ time by greedily assigning intervals to bridge between gaps. We'll describe this process and then come up with a way of simulating it faster than $$$O(n)$$$.

Let's look at the first step of this process. In essence, what happens is that we reach the end $$$b_i$$$ of the first interval, where we have a gap. At this point we assign some number $$$cnt$$$ of ranges (as few as possible) until $$$b_i + X \cdot cnt$$$ is within some other range $$$[a_j, b_j]$$$. Afterwards, continue the process as if starting from $$$j$$$.

Let's compute for each $$$i$$$ some value $$$cnt_i$$$ which is the number of ranges that we need to "bridge the gap" and $$$nxt_i$$$ the corresponding $$$j$$$ that we reach. Because $$$nxt_i > i$$$, the edges $$$(i, nxt_i)$$$ form a tree. Let's build binary lifting on this tree. At this point this should give you enough data to binary search how much up this tree you can go starting from $$$i$$$ such that the total sum of $$$cnt_{(*)}$$$ values doesn't exceed the budget $$$k$$$. The answer if starting from $$$i$$$ is now $$$b_j + X \cdot rem - a_i$$$, where $$$j$$$ is the final position you reach after binary searching, and $$$rem$$$ is the remaining budget (number of ranges).

The only question that remains is how to compute $$$nxt_i$$$ ($$$cnt_i$$$ is easy, just $$$\lceil \frac{a_{nxt_i} - b_i}{X} \rceil$$$). This should be a rather good exercise to come up with a solution yourself. (hint: range DS might help).