如何使用动态编程来解决区间覆盖问题?

我如何使用DP来解决这个算法问题

假设我们有一个大区间,此外我们还有许多小区间(它们都属于这个大区间)。

现在选择这些小间隔,这样它们就不会相互重叠,没有覆盖的区域就不能放在其他小间隔中。

现在我想请他们覆盖这一大面积的最小值

首先输入大间隔的长度(从1开始),然后输入小间隔的数量,然后输入这些小间隔的左右端点。

以下是一个示例:

16 6

1 3个

1 7个

4月15日

8月13日

8 9

2016年11月

输出:

4.

说明:我们选择1-7,8-13。此时,未覆盖的长度为4。

我认为这看起来像经典的KNAPSACK问题,但我无法解决它。