贪心算法（1）：活动安排问题-蒲公英云

贪心算法（1）：活动安排问题

悠悠 2022-02-05 10:21 506阅读 0赞

题目

设有n个活动的集合E＝{1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si＜fi。如果选择了活动i，则它在半开时间区间[si ，fi )内占用资源。若区间[si ，fi )与区间[sj，fj )不相交，则称活动i与活动j是相容的。当 si ≥ fj 或 sj ≥ fi 时，活动i与活动j相容活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。
输入活动数,每个活动的开始结束时间,输出最大相容活动数。

输入：

5
1 2
3 4
5 6
1 4
3 7
输出：
3

题解

首先，将这些活动按照结束时间从小到大排序（不是光把结束时间排序），因为贪心在于每次找的活动都尽可能为后面的活动留更多的时间，然后遍历数组找出所有相容活动。

c++代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define  N 100
#define  true 1
#define  fales 0
struct A
{ 
    int s;
    int f;
};
bool cmp(A a1,A a2)
{ 
    return a1.f<a2.f;
 }
void select(int n,A a[]) { 
    int j=0;
    int sum=1;
    for(int i=1; i<n; i++) { 
        if(a[i].s>=a[j].f) { 
            j=i;
            sum++;
        }
    }
    cout<<sum;
}
int main() { 
    int n;
    cin>>n;
    A a[n];
    for(int i=0; i<n; i++) { 
        scanf("%d",&a[i].s);
        scanf("%d",&a[i].f);
    }
    sort(a,a+n,cmp);
    select(n,a);
}