1
$\begingroup$

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.
$\endgroup$
4
  • 1
    $\begingroup$ Could You please elaborate on "what is maximum intervals that can be covered"? $\endgroup$
    – DirkT
    Dec 9, 2023 at 22:50
  • $\begingroup$ 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. $\endgroup$
    – guitarMan
    Dec 10, 2023 at 5:10
  • $\begingroup$ You mean it covers 12 integers not 12 intervals, right? $\endgroup$
    – DirkT
    Dec 10, 2023 at 6:54
  • 1
    $\begingroup$ My bad, there is definitely some misundertanding in my wording as I use intervals for two different things. $\endgroup$
    – guitarMan
    Dec 10, 2023 at 18:28

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – guitarMan
    Dec 11, 2023 at 12:50
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Jan 10 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.