贪心法：区间覆盖问题

选择尽量少的区间覆盖一条指定的线段[S,T]

在开始的时候把所有区间[S,T]之外的部分切掉

然后将区间按照左端点从小到大排序，如果第一个区间的起点不是S则无解

之后的实现逻辑建议采用本文介绍的这样，否则可能会因为性能差异而T掉

我们记录一个当前延伸的最右位置，初值为S

接下来按顺序考虑每个区间，将其左端点和当前延伸的最右位置进行比较，如果超过了这个最右位置，就不用考虑这个区间了（因为接不上了。。。）

否则我们就计算区间右端点和当前最右位置的差值

我们记录一个最大的差值，然后更新当前的最右位置=原来的最右位置+差值

最后判断最终的最右位置是不是T，从而输出结果

具体实现代码如下：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 const int maxn=1005;
 6 int s,t;
 7 struct Extent
 8 {
 9     int l,r;
10 }a[maxn],e[maxn];
11 bool cmp(Extent x,Extent y)
12 {
13     return x.l<y.l;
14 }
15 int n;
16 int tot=0;
17 int ans=0;
18 int st[maxn];
19 int main()
20 {
21     cin>>s>>t;
22     cin>>n;
23     for(int i=1;i<=n;i++)
24     {
25         cin>>e[i].l>>e[i].r;
26         if(e[i].l>e[i].r)
27             swap(e[i].l,e[i].r);
28         if(e[i].r<s||e[i].l>t)
29         {
30             continue;
31         }
32         if(e[i].l<s)
33             e[i].l=s;
34         if(e[i].r>t)
35             e[i].r=t;
36         tot++;
37         a[tot]=e[i];
38     }
39     sort(a+1,a+tot+1,cmp);
40     if(a[1].l>s)
41     {
42         cout<<0<<endl;
43         return 0;
44     }
45     int maxr=s;
46     while(maxr<t)
47     {
48         int tmp=0;
49         
50         for(int i=1;i<=n;i++)
51         {
52             if(e[i].l>maxr)
53                 break;
54             if(e[i].r-maxr>tmp)
55                 tmp=e[i].r-maxr;
56         }
57         if(tmp!=0)
58         {
59             ans++;
60             maxr+=tmp;
61         }
62         else
63             break;
64     }
65     if(maxr<t)
66         printf("0
");
67     else 
68         printf("%d
",ans);
69     return 0;
70 }