# Dynamic Programming problem about intervals

This is algorithms and data structures assignment and I have been thinking 3 days about it. You are given N sections, placed on numeric axis. Numeric axis is divided by unit intervals. Each section in described by two integers - coordinates of left and right endpoints and it covers corresponding number of intervals. From existing sections, you must remove K sections so that remaining sections in total should cover maximum number of unit intervals. You are given N, K and N different sections. (N<=100000, K<=100). Program should return one integer - maximum possible number of intervals covered by remaining sections after removing K of them. My initial thought was that I needed greedy algorithm because it really looked like scheduling greedy algorithm. But now I understand that it is dynamic programming problem. My most accurate solution is:

1. removing all sections that are covered by another section, since it does not contribute to any maximization or covering intervals.
2. If number of removed sections >= K, then result is currently covered intervals.
3. Otherwise, I implemented dynamic programming using top-down approach with memoization. Solution to current sections (for example, count = M) and K, is maximum among all M-1 sized subsets and K-1; Removing redundant intervals is fast, but recursion increases rapidly and is slow. I could not come up with bottom-up approach. For tabulation method I think it should have K as columns and N as rows and base cases are pretty trivial, but I do not get how to fill grid cells. Any help, hints or advice would be appriciated.
• Could You please elaborate on "what is maximum intervals that can be covered"? Dec 9, 2023 at 22:50
• for example, if we have intervals [1,8], [2,14], [7, 15] and K = 2, we have to remove exactly 2 intervals from them and intervals remaining will cover some unit intervals on grid. In that case if we remove first and last intervals, [2, 14] will cover 12 intervals. In other cases, remaining intervals will cover 7 and 8, so maximum in 12. Dec 10, 2023 at 5:10
• You mean it covers 12 integers not 12 intervals, right? Dec 10, 2023 at 6:54
• My bad, there is definitely some misundertanding in my wording as I use intervals for two different things. Dec 10, 2023 at 18:28

## 1 Answer

It’s difficult. I wouldn’t be surprised at all if it is NP-complete. Many NP-complete problems you can start with things that must be optimal. Like remove all sections covered by another section. Then take all sections that must be optimal: If yo find the k smallest intervals, then take all intervals that are the only coverage for x units where x >= k-smallest interval. Then remove units from the sections that are already covered. For example if you had 101-120 and 115-121 and the k-smallest interval had length 5, 101-120 goes into the solution, and 115-121 is changed to 120-121.

And if this finds no solution then you might pick the largest interval (changing other intervals) until k intervals remain.

• I don't know, I might be wrong because I heard of NP completness only after this problem and It might not be relevant but, some submissions have passed all test cases and have perfect score. Can NP-complete problems pass test cases on big inputs? Dec 11, 2023 at 12:50
• It depends. Take bin packing: If you have bins of size 1000, and lots and lots of small items with a total weight of 9001, then you know they don’t fit in nine bins but will fit easily into 10. I made some suggestions that basically reduce the problem size, if you are lucky the reduce the problem size from 10,000 to very little. I have seen one problem where you had to construct instances very carefully to make it NP-complete. Jan 10 at 7:57