整数区间

1176: (a.in/a.out) 整数区间
题目描述
一个整数区间[A,B]
请编程完成以下任务：
1.从文件中读取区间的个数及其它们的描述；
2.找到满足下述条件的所含元素个数最少的集合中元素的个数,对于每一个区间,都至少
有两个不同的整数属于该集合。
输入
首行包括区间的数目 n,1<=n<=10000,接下来的 n 行,每行包括两个整数 a,b,被一空格隔
开,0<=a<=b<=10000,它们是某一个区间的开始值和结束值。
输出
第一行集合元素的个数,对于每一个区间都至少有两个不同的整数属于该区间,且集合所包含
元素数目最少。
样例输入
43
6
2 4
0 2
4 7
样例输出
4

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8          int x;
 9          int y;
10 }b[10005];
11 int cmp(node a,node b)
12 {
13          return a.x < b.x;
14 }
15 int main()
16  {
17         freopen("a.in","r",stdin);
18          freopen("a.out","w",stdout);
19         int sum = 1,i,n,p;
20         scanf("%d",&n);
21         for(i = 1;i <= n;i++)
22         {
23                 scanf("%d %d",&b[i].x,&b[i].y);
24           }
25           sort(b+1,b+1+n,cmp);
26           p = -2;
27      for(int i=1;i<=n;i++)//p是目前的右端点 ,p要取个负的因为区间左端点取得到0 
28      {
29          if(b[i].x > p-2)//能覆盖就继续跳过这个操作
30         {
31                           sum++;
32                           p = b[i].y;//否则数量+1，修改目前的右端点
33                   } 
34     }
35      printf("%d",sum);
36  
37  }

***当初考试的时候好不容易读懂了题but是在想不出肿么做。。于是固定输出四。。竟然五十分。大概是人品大爆发了叭。

***后来发现可以把它想象成木板。排好序钉钉子，每个钉两个钉子

1. 把数组排序

排好序了就要开始钉钉子，当然作为最少的钉钉子法的话一定是钉最后面那块，于是乎就把p设为最后面，因为要钉两个钉子，假如后面的那块板子和这块板子距离大于两个钉子的距离，则就要再钉一个钉子。

2. 循环判断是否需要钉钉子，需要就加一。