题目描述

There is a collection of n activities E={1,2,..,n}, each of which requires the same resource, such as

a lecture venue, etc., and only one activity at a time Use this resource. Each activity i has a start

time of si and an end time of fi and si<fi. If the activity i is selected, it occupies resources within

the time interval [si,fi). If the interval [si,fi) does not intersect the interval [sj,fj), then the activity i is

said to be compatible with the activity j. That is, when fi<=sj or fj<=si, the activity i is compatible

with the activity j . Choose the largest collection of activities that are compatible with each other.

输入格式

The first line is an integer n;

The next n line, two integers per line, si and fi.

输出格式

Excluding mutual and compatible maximum active number.

样例输入1

4

1 3

4 6

2 5

1 7

样例输出1

2

数据范围与提示

1<=n<=1000

 

这道题解法与杭电今年暑假不AC解法相同，采用贪心法

代码实例

#include
     
      struct huodong{    int begin;    int end;} J[1002];int main(){    int n,i,j,sum,temp;    sum = 1;    scanf("%d",&n);    for(i=0; i
      
       J[j+1].end)            {                temp = J[j].end;                J[j].end = J[j+1].end;                J[j+1].end = temp;                temp = J[j].begin;                J[j].begin = J[j+1].begin;                J[j+1].begin = temp;            }        }    }    temp = J[0].end;    for(i=1; i
       
        =temp)        {            sum++;            temp = J[i].end;        }    }    printf("%d\n",sum);    return 0;}