Hello, beautiful people of Codeforces.

Yesterday I spent several hours trying to solve the following problem, which feels that should be an easy dp. I then tried to search it on Google and failed. I feel like it's almost impossible to find solutions to algorithmic problems via search engines, they always return stuff that matches with one or two words from the statement but not the problem itself. Anyway, here's the problem:

You are given $$$n$$$ line segments $$$[l_i, r_i]$$$ ($$$1 \leq l_i \leq r_i \leq 2n$$$) and a number $$$k$$$. You are allowed to select $$$k$$$ points on the number line. What is the maximal number of segments that conitain at least one of the selected points you can obtain?

Example:

6
1 7
3 5
6 8
2 7
7 11
10 12
2

The answer is 5. We can select points 4 and 7, hitting all segmets but the last one. Hitting all segments is impossible, as [3, 5], [6, 8] and [10, 12] are disjoint. Note that even though segment [1, 7] is hitted twice, it is only counted towards the solution once.

We are also given that $$$k$$$ is much less than $$$n$$$. I expect the solution to run in $$$\mathcal{O}(nk)$$$ with possibly some $$$\log$$$ s.

Note 1: When k = 1 this is a well know problem and can easily be solved in $$$\mathcal{O}(n \log n)$$$:

1. Create $$$2n$$$ event of the form $$$(l_i, +1)$$$ and $$$(r_i, -1)$$$;
2. Sort the events by the first coordinate;
3. The answer is the maximal sum of the second coordinate over the events with the first coordinate up to some $$$i$$$ (this can be computed with a single loop);

Note 2: I called it a "dual" problem to another well know problem: Given $$$n$$$ line segments $$$[l_i, r_i]$$$ ($$$1 \leq l_i \leq r_i \leq 2n$$$), what is the minimal number of points to hit all the segments?

This "primal" problem is easily solvable in $$$\mathcal{O}(n \log n)$$$ by a greedy, selecting always the first end of not-yet-hit segments.