当前位置：首页 > article >正文

贪心算法：经典活动安排问题

article 2024/11/14 17:37:27

来源：加码未来模拟试卷

这是一个经典的活动安排问题，本质上是一个贪心算法问题。本文给出了C++ 和Python的代码实现。C++代码解析对不同数据结构的实现进行对比说买，总结了C++内存管理的关键。Python代码解析还给出了测试用例。最后专门用一节对贪心算法的应用场景进行了分析，列出了适用和不适用场景。

题目描述

放假了，小浩在放假时有许多活动可以选择，每个活动都有一个开始时间和结束时间，如果选择了某个活动，那么从开始到结束的这段时间都不能做其他事情了。假如某项活动的开始时间刚好等于另一项活动的结束时间，是可以都参加的。现在给出各项活动的时间安排，请问，小浩最多可以参加几项活动。

输入

第一行一个整数 $n$ ，表示活动数目接下来 $n$ 行，每行两个整数 $s$ ， $t$ 表示活动的起始时间和终止时间。
$1 <= n <= 1000$
$0<s<t<10^9$

输出

一个整数表示答案

输入样例

输出样例

算法分析

算法思想

这是一个经典的活动安排问题，解决方案使用了贪心算法的思想，主要步骤如下：

首先将所有活动按照结束时间排序
选择第一个结束最早的活动
然后遍历剩余活动，如果当前活动的开始时间大于等于上一个选择的活动的结束时间，就选择这个活动
统计总共选择的活动数量

贪心策略分析

为什么按结束时间排序是最优的？

结束时间早的活动会给后面留下更多空间
如果选择结束时间晚的，可能会错过多个结束时间早的活动

示例分析

对于样例输入：

程序会这样处理：

首先将活动按结束时间排序：(1,3), (2,5), (4,6), (1,7)
选择第一个活动(1,3)
然后检查剩余活动，发现(4,6)可以参加（因为开始时间4大于3）
最终可以参加2个活动

注意：当某个活动的开始时间等于另一个活动的结束时间时，这两个活动是可以都参加的

数据类型

输入的时间范围很大（可以到10^9）

C++ 中要使用 long long 类型
Python的整数类型可以正确处理这个范围的数字

代码实现

C++ 代码

1. 方法一

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义活动结构体
struct Activity {
   
    long long start, end;
    
    // 重载小于运算符，用于排序
    bool operator < (const Activity& other) const {
   
        return end < other.end;
    }
};

int maxActivities(int n, vector<Activity>& activities) {
   
    // 按照结束时间排序
    sort(activities.begin(), activities.end());
    
    // 记录已选择的活动数量
    int count = 1;
    // 记录上一个选择的活动的结束时间
    long long lastEnd = activities[0].end;
    
    // 遍历所有活动
    for(int i = 1; i < n; i++) {
   
        // 如果当前活动的开始时间大于等于上一个活动的结束时间
        if(activities[i].start >= lastEnd) {
   
            // 选择当前活动
            count++;
            lastEnd = activities[i].end;
        }
    }
    
    return count;
}

int main() {
   
    ios::sync_with_stdio(false);  // 优化输入输出速度
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 读取所有活动
    vector<Activity> activities(n);
    for(int i = 0; i < n; i++) {
   
        cin >> activities[i].start >> activities[i].end;
    }
    
    // 计算并输出结果
    cout << maxActivities(n, activities) << endl;
    
    return 0;
}

2. 方法二

#include <iostream>
using namespace std;

// 定义活动结构体
struct Activity {
   
    long long start;
    long long end;
};

// 快速排序的分区函数
int partition(Activity arr[], int low, int high) {
   
    Activity pivot = arr[high];
    int i = low - 1;
    
    for(int j = low; j < high; j++) {
   
        if(arr[j].end <= pivot.end) {
   
            i++;
            // 交换元素
            Activity temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp