活动安排 贪心算法

会议（活动）安排

如题：

思路：

贪心算法

假设现在有五组数据

1.将活动按照结束时间递增排序

2.当前安排的活动的结束时间小于等于下一个活动的开始时间

ps：如果两个活动的结束时间相同，选择开始时间较晚的

选出 a1 和 a4

有两个时间所有选择使用结构体

#include<stdio.h>
#include<stdlib.h>

//活动有开始和结束时间，用结构体来存
typedef struct{

    int start;
    int end;

} Activity;

//比较函数，用于排序活动
int compare(const void* a, const void* b){

    // a,b 表示要进行比较的两个活动
    //强制类型转换
    Activity* activityA = (Activity*)a;
    Activity* activityB = (Activity*)b;
    
    return (activityA->end - activityB->end);
}

int scheduleActivities(Activity activities[], int n){

    // 按照活动结束时间从早到晚进行排序
    qsort(activities, n, sizeof(Activity), compare);

    int count = 1;  //初始化计数器为 1 ,已安排的活动数量
    int end_time = activities[0].end;  //初始化end_time为第一个活动的结束时间

    //遍历每个活动
    for (int i = 1; i < n; i++){

        if (activities[i].start >= end_time){

            count++;
            end_time = activities[i].end;

        }
    }

    return count;  
}

int main(){

    int m;
    scanf("%d", &m); //组数
    int j = 0;

    for (int t = 0; t < m; t++){

        int n;
        scanf("%d", &n);  //每组测试数据的活动数量

        Activity activities[n];

        //获取每个活动的起始和结束时间
        for (int i = 0; i < n; i++){

            scanf("%d %d", &activities[i].start, &activities[i].end);

        }

        int ans = scheduleActivities(activities, n);
        
        //PTA的换行，我真的阐述你的梦
        if(j == ans-1){
            printf("%d", ans);
        }
        else{
            
            printf("%d\n", ans);
        }
        j++;
    }

    return 0;
}