PAST1N

https://gyazo.com/8b99c6809b86f9fe2fee2cd6710f2b46

Thoughts.

I want to minimize the sum of the removal costs of N overlapping intervals by moving intervals of length C

I haven't proved it properly, but I think the starting point of C is either 0 or the endpoint of the other interval + 1.

OK if the cost can be calculated in smaller orders for each section.

Finding overlapping intervals is a linear order if done naively.

For two sets of numbers, given their respective inequality constraints, do you want to enumerate those that satisfy both?

Sometimes it's too late for enumeration, or for example, the case where all the sections overlap.

Sort by mixing (position, ID, isStartPoint) of start and end points

If you advance the endpoint and step on the starting point, add the cost.

If you advance the starting point and step on the end point, reduce the cost.

Which one to advance is determined by "whether the starting point is advanced to a length less than C

This is now obtained in linear order.

Official Explanation OK

---