【题目描述】

数轴上有n个闭区间[ai, bi]，取尽量少的点，使得每个区间内都至少有一个点。（不同区间内含的点可以是同一个，1<=n<=10000，1<=ai<=bi<=10^9）。求最少点的个数。

【输入】

n

n项工作的开始与结束时间

【输出】

最多参与的工作项数

【输入样例1】

4  3 13  6 20  4 14  1 10

【输出样例1】

1

【输入样例2】

3  4 7  6 8  11 20

【输出样例2】

2

1.辗转相除法

int gcd(int a,int b)     {        if(a%b==0)           return b;       else           return gcd(b,a%b);   }

2.穷举法

int divisor (int a, int b) //自定义函数求两数的最大公约数     {        int  temp;//定义整型变量       temp=(a>b)?b:a;//采种条件运算表达式求出两个数中的最小值       while(temp>0)          {                if(a%temp==0&&b%temp==0)//只要找到一个数能同时被a,b所整除，则中止循环                break;                temp--;//如不满足if条件则变量自减，直到能被a,b所整除         }        return (temp);//返回满足条件的数到主调函数处     }

3.更相减损法

 int gcd2(int m,int n)   {       int i=0,temp,x;       while(m%2==0&&n%2==0)//判断m和n能被多少个2整除      {           m/=2;           n/=2;           i+=1;      }        if(m<n)//m保存大的值     {          temp=m;          m=n;          n=temp;     }        while(x)     {          x=m-n;          m=(n>x)?n:x;          n=(n<x)?n:x;          if(n==(m-n))          break;     }      if(i==0)      return n;          else          return (int) pow(2,i)*n;    }

4.其他方法

int gcd(int a,int b)  {      int c;      while(b)      {          c=a%b;          a=b;b=c;      }      return a;  }