ACM winter vacation training 6

Greedy Algorithm

Greedy Algorithm （ Also known as greedy algorithm ） Refer to , In solving the problem , Always make what seems to be the best choice at the moment . Greedy algorithm can not get the overall optimal solution for all problems , The key is the choice of greedy strategy , in other words , Don't take into account the overall optimum , The algorithm obtains the local optimal solution in a sense .

Algorithm ideas

Greedy algorithm generally follows the following steps ：
① Build a mathematical model to describe the problem .
② Divide the problem into several sub problems .
③ Each subproblem is solved , Get the local optimal solution of the subproblem .
④ Synthesize the local optimal solution of the subproblem into a solution of the original solution .
Greedy algorithm is a simpler solution to some problems 、 Faster design technology . Greedy algorithm is characterized by step by step , It is often based on the current situation and makes the optimal choice according to an optimization measure , Regardless of the possible overall situation , It saves a lot of time that must be spent trying everything possible to find the optimal solution . The greedy algorithm adopts top-down , Make successive greedy choices in an iterative way , Every greedy choice , The problem is reduced to a smaller subproblem , Through every step of greedy choice , An optimal solution of the problem can be obtained . Although it is necessary to ensure that the local optimal solution can be obtained at each step , However, the resulting global solution is sometimes not necessarily optimal , So greedy algorithms don't go back .

Conditions of use

The problems solved by greedy method should have the following 2 Features .
1、 Greedy choice nature
The global optimal solution of a problem can be achieved by selecting a series of local optimal solutions , And each choice can depend on the choice made before , But it doesn't depend on the choices to be made later . This is the nature of greedy choice . For a specific problem , To determine whether it has the nature of greedy choice , It must be proved that the greedy choice made at each step leads to the global optimal solution of the problem .
2、 Optimal substructural properties
When the optimal solution of a problem contains the optimal solution of its subproblem , We call this problem an optimal substructure . The property of optimal substructure is the key to solve the problem by greedy method . in application , As for what question has what kind of greedy choice nature is uncertain , Need specific analysis .

Title Example

“ This summer vacation is not good AC？”
“ Yes .”
“ So what are you doing ？”
“ Watch the world cup , Idiot ！”
“@#$%^&*%…”

Such is the case , Here comes the world cup , Fans' Festival is coming too , It's estimated that a lot of ACMer And I'll leave the computer alone , I'm on TV .
As a fan , I want to see as many complete games as possible , Of course , As a good youth in the new era , You're going to watch some other shows , Like the news network （ Never forget to care about national affairs ）、 very 6+7、 Super girl , And Wang Xiaoya's 《 Happy Dictionary 》 wait , Suppose you already know the schedule of all your favorite TV shows , Will you make a reasonable arrangement ？（ The goal is to see as many full shows as possible ）

Input

Input data contains multiple test instances , The first line of each test instance has only one integer n(n<=100), The total number of programs you like to watch , And then there was n Row data , Each row contains two data Ti_s,Ti_e (1<=i<=n), Separate indication control i The start and end time of a program , To simplify the problem , Each time is represented by a positive integer .n=0 End of input , Don't deal with it .

Output

For each test case , Output the number of TV programs that can be seen completely , The output of each test instance takes up one line .

Sample Input

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0

Sample Output

5

Code example

#include<stdio.h>
int main()
{
    
	int n;
	while(scanf("%d",&n)!=EOF&&n!=0)// Multi group input 
	{
    
		int a[110],b[110],i,j,k,t,num=1;
		for(i=0;i<n;i++)
		scanf("%d %d",&a[i],&b[i]);
		for(i=0;i<n-1;i++)// Sort by end time 
		{
    
			k=i;
			for(j=i+1;j<n;j++)
			{
    
				if(b[k]>b[j])// Find the program that ends earliest 
				k=j;
			}
			t=a[i];// Switch the earliest programs to the front 
			a[i]=a[k];
			a[k]=t;
			t=b[i];
			b[i]=b[k];
			b[k]=t;
		}
		j=0;
		for(i=1;i<n;i++)// If the program time does not conflict num++
		{
    
			if(b[j]<=a[i])
			{
    
			num++;
			j=i;
			}
		}
		printf("%d\n",num);// Output 
	}
	return 0;
}