You would like to implement kossaraju for calculating strongly connected components, however the graph is fairly big. You do a normal DFS with speedup in finding edges to unvisited vertices. You want a data structure for this. Although it seems like an ugly 2D problem, you can notice that it's enough to search for edges independently and use a "find max on an interval segment tree" to find the best candidate.

First of all, I hope you thought about keeping only useful segments, the ones that doesn't include any other one. It is a very classical thing to do. This allows us to have all segments strictly sorted by $$$l$$$ and strictly sorted by $$$r$$$ at the same time. It is not necessary for this problem but it helps visualization.

About the point of view: it's hard to solve this problem focusing on the segments as a whole two-dimensional object, probably some unsolvable issues will quickly arise if you try this way and you will get stuck. So, it's time to consider another point of view!

There is only one other meaningful possible point of view: focusing on points instead. $$$m$$$ is large, but you can compress the line into $$$\mathcal{O}(n)$$$ weighted points (weight = size of the compressed interval).

When we have to create a dp state over points, trying to find an optimal set of points, $$$dp_x$$$ is often something like "how to satisfy all constraints after $$$x$$$, assuming $$$x$$$ is a chosen point and everything before is OK".

The rightmost already chosen point is a relevant parameter because it's the only thing we need to remember in order to "continue the exploration (the construction of the set)".

The transition will obviously be "choose the next point $$$y > x$$$". It is a classical type of DP.

The order in which we choose the crosses don't matter, so let's choose them from left to right.

For a given position $$$x$$$, assuming that all segments satisfying $$$r_i < x$$$ are already covered and that there is a cross on point $$$x$$$, let $$$opt_x$$$ be the minimum number of crosses we have to put in order to cover all remaining segments, the ones at the right of $$$x$$$ ($$$x < l_i$$$).

The transition is obviously "choosing where to put the next cross after $$$x$$$".

We can greedily compute $$$opt$$$ (finding ONE optimal transition, the righmost valid one works since $$$opt$$$ is non-increasing). Let $$$cnt_x$$$ denote the number of ways to do this optimally.

You must find a clear description of ALL the optimal dp transitions. For a fixed last point $$$x$$$, what can be the optimal next point $$$y > x$$$? Find two conditions $$$y$$$ must satisfy.

The next point $$$y > x$$$ must satisfy these two conditions:

• there must be no segment such that $$$x < l_i < r_i < y$$$, otherwise it will not be covered (there is a "gap" between $$$x$$$ and $$$y$$$).

• $$$opt_y = opt_x - 1$$$

It's obviously an interval:

• The first condition only fix an upper bound $$$y_{max}$$$, the minimum $$$r_i$$$ over all $$$i$$$ such that $$$x < l_i$$$. Notice that $$$y_{max}$$$ is the rightmost valid transition, so we can set $$$opt_x := opt_{y_{max}} + 1$$$.

• Since $$$opt$$$ is non-increasing, the second condition fix a lower bound $$$y_{min}$$$, the leftmost point such that $$$opt_{y_{min}} = opt_x - 1$$$.

We can see that $$$cnt_x = w_x \cdot (\sum cnt_y)$$$, where $$$w_x$$$ is the weight of the point $$$x$$$ (the size of the original interval we compressed in part 1) and $$$y_{min} \le y \le y_{max}$$$.

How to effeciently compute the array $$$cnt$$$? What will be the final answer?

We will compute $$$cnt$$$ in decreasing order. The bounds $$$y_{min}$$$ and $$$y_{max}$$$ can only move left during the process, so we can maintain them and maintain the sum of $$$cnt_y$$$ between these bounds in amortized linear time ("two pointers" technique).

The final answer will be $$$cnt_0$$$, where $$$0$$$ is a fictive position.

This solution has a final time complexity of $$$\mathcal{O}(n \log n)$$$, which would be $$$\mathcal{O}(n)$$$ if we didn't have to compress coordinates.