信息学奥赛一本通T1323:贪心算法 活动选择

【题目描述】学校在最近几天有n个活动,这些活动都需要使用学校的大礼堂,在同一时间,礼堂只能被一个活动使用。由于有些活动时间上有冲突,学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。【输入】第一行一个整数n(n≤1000);接下来的n行,每行两个整数,第一个begini,第二个是endi(begini<endi≤32767)。【输出】输出最多能安排的活动个数。【输入样例】11【输出样例

信息学奥赛一本通T1323:活动选择

【题目描述】

学校在最近几天有n个活动,这些活动都需要使用学校的大礼堂,在同一时间,礼堂只能被一个活动使用。由于有些活动时间上有冲突,学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。

现在给出n个活动使用礼堂的起始时间begini和结束时间endi(begini<endi),请你帮助办公室人员安排一些活动来使用礼堂,要求安排的活动尽量多。

【输入】

第一行一个整数n(n≤1000);

接下来的n行,每行两个整数,第一个begini,第二个是endi(begini<endi≤32767)。

【输出】

输出最多能安排的活动个数。

【输入样例】

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

【输出样例】

4

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 1001
using namespace std;
int n;
int beginn[N],endd[N];
void qsort(int x,int y)
{
    int i,j,mid;
    i=x;
    j=y;
    mid=endd[(x+y)/2];
    while(i<=j)
    {
        while(endd[i]<mid)
            i++;
        while(endd[j]>mid)
            j--;
        if(i<=j)
        {
            swap(endd[j],endd[i]);
            swap(beginn[j],beginn[i]);
            i++;
            j--;
        }
    }
    if(x<j)
        qsort(x,j);
    if(i<y)
        qsort(i,y);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>beginn[i]>>endd[i];
    qsort(1,n);

    int cnt=0;
    int temp=-INF;
    for(int i=1;i<=n;i++)
        if(beginn[i]>=temp)
        {
            cnt++;
            temp=endd[i];
        }
    cout<<cnt<<endl;
    return 0;
}

 

信息学奥赛一本通T1323:贪心算法 活动选择 归属于 贪心算法,更多同类题解源程序见:贪心算法 和 活动选择

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章